Tricki

## Revision of I want to find a non-trivial solution to a system of equations from Sat, 09/05/2009 - 18:27

Suppose one wants to find a solution in some class (such as a vector space) to some system of equations, e.g.

In some cases, there will be an obvious "trivial" solution (e.g. ), but one is interested in locating a "non-trivial" solution. There are a variety of ways that this can be done.

• Degree of freedom arguments. If the "dimension" of is larger than the number of constraints in the system, then one can sometimes establish non-trivial solutions quite easily, especially if the system is linear (or approximately linear).

• Collision arguments. This is related to the degrees of freedom argument. If one can use a non-trivial collision to generate a non-trivial solution to the desired system, then the pigeonhole principle (or dimensional arguments) will give a solution as soon as the cardinality (or dimension) of the domain of exceeds that of the range.

• Divisibility arguments In some cases one can show for free that the number of solutions is divisible by some prime ; thus, once one has one trivial solution, one must have non-trivial solutions as well. The Chevalley-Warning theorem is particularly useful for this sort of argument.

• Topological arguments The intersection number (counting multiplicity) of the surfaces is often stable with respect to topological deformations and so can be studied by the tools of intersection cohomology. (Need more discussion here - not qualified to present it.)

• Complex analytic arguments There are various complex-analytic ways to force the existence of solutions to equations such as , such as the argument principle. There are also various ways to deform the system to a simpler system while preserving the number of solutions, using tools such as Rouche's theorem.

### Example 1

Problem: Let be a subset of , where is a finite field. Show that is contained in a hypersurface of degree , where is the cardinality of (and the implied constant can depend on ).

Solution: What we are asking for here is to find a non-trivial polynomial of degree at most for some which vanishes at every point of . But one can view the space of polynomials of degree at most as a vector space of dimension about , and the requirement that a polynomial vanish at every point of can be viewed as a set of homogeneous linear constraints on this vector space. Linear algebra then tells us that a non-trivial solution exists as soon as the dimension of the space (i.e. the degrees of freedom) exceeds , and the claim follows.

This result, incidentally, is used in Dvir's proof of the finite field Kakeya conjecture; see this blog post for further discussion.

### Example 2

(Kronecker approximation theorem - this is an "entropy" version of this general method, where we deal with approximate solutions to a problem rather than exact ones.)