4
$\begingroup$

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!

Improve this question
$\endgroup$
9
  • $\begingroup$ @Siming: Why don't you think before you add examples of equations? Ben Green gave a non-trivial example before. $\endgroup$
    – user6976
    Commented May 22, 2012 at 14:27
  • 1
    $\begingroup$ @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. $\endgroup$
    – Siming Tu
    Commented May 22, 2012 at 14:52
  • 1
    $\begingroup$ 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. $\endgroup$
    – Ben Green
    Commented May 22, 2012 at 15:29
  • $\begingroup$ Inspection modulo 12 suggests that 5/6 (all not divisible by 6) is also doable. $\endgroup$
    – user9072
    Commented May 22, 2012 at 15:44
  • 1
    $\begingroup$ 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. $\endgroup$
    – Ben Green
    Commented May 22, 2012 at 16:34

5 Answers 5

Reset to default
6
$\begingroup$

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

Improve this answer
$\endgroup$
4
$\begingroup$

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.

Improve this answer
$\endgroup$
1
  • $\begingroup$ 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. $\endgroup$
    – Siming Tu
    Commented May 24, 2012 at 0:36
3
$\begingroup$

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.

Improve this answer
$\endgroup$
2
  • $\begingroup$ 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? $\endgroup$
    – Ben Green
    Commented May 22, 2012 at 16:25
  • $\begingroup$ @Ben: You are correct. $\endgroup$
    – user6976
    Commented May 22, 2012 at 16:56
2
$\begingroup$

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.

Improve this answer
$\endgroup$
1
  • $\begingroup$ 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. $\endgroup$
    – user6976
    Commented May 24, 2012 at 1:04
0
$\begingroup$

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

Improve this answer
$\endgroup$
1
  • $\begingroup$ oh well...but guess this is kind of contrived... $\endgroup$
    – user22202
    Commented May 23, 2012 at 3:04

You must log in to answer this question.

Not the answer you're looking for? Browse other questions tagged .