MathOverflow is a question and answer site for professional mathematicians. Join them; it only takes a minute:

Sign up
Here's how it works:
  1. Anybody can ask a question
  2. Anybody can answer
  3. The best answers are voted up and rise to the top

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$?


share|cite|improve this question
@Siming: Why don't you think before you add examples of equations? Ben Green gave a non-trivial example before. – Mark Sapir May 22 '12 at 14:27
@Mark Sapir: I'm sorry that I did not think much when I gave examples. For the equation $x^2+y^2=z^2$, there is a set of density 1/2 such that the equation does not have any solution in it. However, we can still ask how large the density can be, I add a note in my question. – Siming Tu May 22 '12 at 14:52
Siming, I think that taking the squares $x^2$ with $x$ either odd or $\equiv 2 \mod{4}$ gives you a set consisting of $\frac{3}{4}$ of the squares with no solution to $x^2 + y^2 = z^2$ (look mod $8$). Probably it's true that if you take $99 \%$ of the squares then there's a solution to $x^2 + y^2 = z^2$. I don't immediately have a feel for whether this is doable or not; I'll get back to you. Certainly use of the circle method will be problematic if one proceeds naively. – Ben Green May 22 '12 at 15:29
Inspection modulo 12 suggests that 5/6 (all not divisible by 6) is also doable. – user9072 May 22 '12 at 15:44
In fact there is no set of size $o(N)$ which misses all triples $(3k, 4k, 5k)$ by the following type of argument: consider such triples with $|k - N/10| < N/100$ (say). These are all disjoint. Therefore any set consisting of $98\%$ of ${1,..,N}$ contains a pythagorian triple. Computation of the exact density might be tricky. – Ben Green May 22 '12 at 16:34

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 Arithmetic Progressions of Squares

share|cite|improve this answer

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.

share|cite|improve this answer
I think this is a very interesting problem. We also have the quantitative version of it. We can ask that how large a set should be to insure that it contains a polynomial progression of length k. – Siming Tu May 24 '12 at 0:36

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.

share|cite|improve this answer
Mark, for the Pell equation there is a huge set $A$, of size $N - O(\log N)$, just by deleting all $x$ and $y$ that are solutions to the Pell equation? – Ben Green May 22 '12 at 16:25
@Ben: You are correct. – Mark Sapir May 22 '12 at 16:56

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.

share|cite|improve this answer
The equation $(a+b-2c)(a^2+b^2+c^2)=0$ is also not linear but every arithmetic progression $a,c,b$ satisfies it. Of course your equation is better because your polynomial is not reducible. – Mark Sapir May 24 '12 at 1:04

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

share|cite|improve this answer
oh well...but guess this is kind of contrived... – user22202 May 23 '12 at 3:04

Your Answer


By posting your answer, you agree to the privacy policy and terms of service.

Not the answer you're looking for? Browse other questions tagged or ask your own question.