Nonlinear equations in integers - MathOverflow most recent 30 from http://mathoverflow.net 2013-06-19T14:58:41Z http://mathoverflow.net/feeds/question/97662 http://www.creativecommons.org/licenses/by-nc/2.5/rdf http://mathoverflow.net/questions/97662/nonlinear-equations-in-integers Nonlinear equations in integers Siming Tu 2012-05-22T13:56:53Z 2012-05-23T04:08:58Z <p>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.</p> <p>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*}</p> <p>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. </p> <p>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$? </p> <p>Thanks!</p> http://mathoverflow.net/questions/97662/nonlinear-equations-in-integers/97665#97665 Answer by Mark Sapir for Nonlinear equations in integers Mark Sapir 2012-05-22T14:02:57Z 2012-05-22T14:25:17Z <p>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. </p> http://mathoverflow.net/questions/97662/nonlinear-equations-in-integers/97666#97666 Answer by Ben Green for Nonlinear equations in integers Ben Green 2012-05-22T14:15:20Z 2012-05-22T14:15:20Z <p>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 <a href="http://mathoverflow.net/questions/78949/" rel="nofollow">http://mathoverflow.net/questions/78949/</a></p> http://mathoverflow.net/questions/97662/nonlinear-equations-in-integers/97671#97671 Answer by quid for Nonlinear equations in integers quid 2012-05-22T15:07:32Z 2012-05-22T15:07:32Z <p>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 href="http://arxiv.org/abs/math/0610050" rel="nofollow">a paper due to Tao and Ziegler</a>, proving such a result for the primes, contains various information on this type of problems. </p> http://mathoverflow.net/questions/97662/nonlinear-equations-in-integers/97712#97712 Answer by unknown (google) for Nonlinear equations in integers unknown (google) 2012-05-23T02:24:14Z 2012-05-23T02:59:36Z <p>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&lt;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$.</p> <p>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 <code>$\{1,\dots,N\}$</code>. There are no solutions since $-1$ is not a square $\bmod p$.</p> <p>But if $p$ is fixed, then one wonders how much larger $b$ can be beyond size $\frac{p-1}{p}$.</p> http://mathoverflow.net/questions/97662/nonlinear-equations-in-integers/97716#97716 Answer by Mark Lewko for Nonlinear equations in integers Mark Lewko 2012-05-23T04:03:29Z 2012-05-23T04:08:58Z <p>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.</p>