Nonlinear equations in integers - MathOverflow

Nonlinear equations in integers

2012-05-22T13:56:53Z

Linear patterns in subset of the integers (for example, primes) such as arithmetical progressions is a hot topic in mathematics. Recently, much progress has been made in this area. For example, the next result of T. Sanders(in the paper "On Roth's theorem on progressions") gives a estimate of how large can a set be to make sure that it does not contain no non-trivial three-term arithmetic progressions.

Suppose that $A \subset \lbrace 1,\dots,N\rbrace$ contains no non-trivial three-term arithmetic progressions. Then \begin{equation*} |A| = O\left(\frac{N (\log \log N)^5 }{\log N}\right). \end{equation*}

My question is related to this result. For Roth's theorem we consider a linear equation. If we consider nonlinear equation, such as $x^2+y^2=z^2$ or $x^2-2y^2=1$, we can ask the same problems: Suppose that $A \subset \lbrace 1,\dots,N\rbrace$, if a nonlinear equation has no non-trivial solution in $A$, how large can it be. So my question is that whether there is any result about this problem.

Note: For equation $x^2+y^2=z^2$, it is not hard to prove that $A$ can have $N/2$ numbers. (Thank Mark Sapir for reminding me of this fact) So $|A|$ can be $O(N)$. But maybe we can consider this problem: for $b$ close to 1, if $N$ is sufficiently large and $|A|\geq bN$, can there be no non-trivial solution in $A$?

Thanks!

Answer by Mark Sapir for Nonlinear equations in integers

2012-05-22T14:02:57Z

For your equation $x^2+y^2=z^2$, $A$ can have $N/2$ numbers. For example, take all odd numbers $\le N$. This set does not have any solutions of your (Pythagorean) equation. For the new (Pell) equation, the set of even numbers will do the trick.

Answer by Ben Green for Nonlinear equations in integers

2012-05-22T14:15:20Z

Mark Sapir's point is of course valid. The equation $x^2 + y^2 = 2z^2$ is a different matter. There was a discussion of this previously on Math Overflow: see http://mathoverflow.net/questions/78949/

Answer by quid for Nonlinear equations in integers

2012-05-22T15:07:32Z

This is in a slightly different direction, but you might still be interested. There are results on Polynomial Progressions (instead of arithmetic ones). More specifically, there is an extension of Szemerédi's Theorem to Polynomial Progressions due to Bergelson and Leibman; the introduction of a paper due to Tao and Ziegler, proving such a result for the primes, contains various information on this type of problems.

Answer by unknown (google) for Nonlinear equations in integers

2012-05-23T02:24:14Z

Hi! Not sure if this is exactly what you are asking for, but for non-linear equations in three variables you can fix a $b<1$ arbitrarily close to $1$ and then construct an equation so that $|A| > bN$ and there are no solutions to the equation in $A$, by using congruence conditions as was done for $x^2+y^2=z^2$.

Take $x^2+y^2=p^2z^2$ for $p\equiv 3 \bmod 4$, $p$ sufficiently large, and form $A$ by deleting $p\mathbb{Z}$ from $\{1,\dots,N\}$ . There are no solutions since $-1$ is not a square $\bmod p$.

But if $p$ is fixed, then one wonders how much larger $b$ can be beyond size $\frac{p-1}{p}$.

Answer by Mark Lewko for Nonlinear equations in integers

2012-05-23T04:03:29Z

The polynomial form of Roth's theorem (previously mentioned by Quid) implies, for instance, that any set of positive density contains a triple $x$, $x+h$, $x+h^2$ (for $h\neq 0$). Notice that this is equivalent to asking for solutions to the nonlinear equation $b^2+b+a^2=c+2ab$. So results of this form do hold for some nonlinear equations.