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

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

Sat, 15/08/2009 - 22:27 — neroden

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...