Tricki
a repository of mathematical know-how

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

Stub iconThis article is a stub.This means that it cannot be considered to contain or lead to any mathematically interesting information.

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

 f_1(x) = \ldots = f_d(x) = 0.

In some cases, there will be an obvious "trivial" solution (e.g. x=0), 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 V 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 F(x)=F(y) 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 F 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 p; 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  f_i(x) = 0 \} 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 f(z)=0, 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 E be a subset of F^n, where F is a finite field. Show that E is contained in a hypersurface of degree O( |E|^{1/n} ), where |E| is the cardinality of E (and the implied constant can depend on n).

Solution: What we are asking for here is to find a non-trivial polynomial P of degree at most d for some d = O(|E|^{1/n}) which vanishes at every point of E. But one can view the space of polynomials of degree at most d as a vector space of dimension about O(d^n), and the requirement that a polynomial vanish at every point of E can be viewed as a set of |E| 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 |E|, 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.)

Comments

Article structure

This should probably be restructured to match the form of the articles under "What kind of problem am I trying to solve?". I might even do so myself if I have the time and energy...