User alex rice - MathOverflow

Answer by Alex Rice for Sequences of Squares with all square differences

2011-08-21T21:12:16Z

To clarify, this question arose when my adviser Neil Lyall and I were attempting to provide simple upper bounds on the size of the LARGEST subset of $ [1,2,...,N] $ with NO square differences, for the purposes of an introduction to a talk about generalizations of the Sarkozy-Fursternburg Theorem, which states that this quantity is $o(N)$.

In particular, if $S$ is the set of squares, $A \subset [1,2,...,N] $ with $(A-A) \cap S = \emptyset $, and $a_1 < a_2< ... < a_k$ is any collection of non-negative integers such that $a_i-a_j \in S$ whenever $i > j$, then the sets $A+a_1$, $A+a_2,...A+a_k$ are all pairwise disjoint. Therefore, $|A| \leq (N+a_k)/k$. If such a collection was possible for every $k$, then this would immediately provide a remarkably (perhaps disturbingly) elementary proof of the Sarkozy-Fursterberg Theorem that would not require any of the harmonic analysis or ergodic theory tools utilized in other proofs.

Notice that the statement that such a collection of non-negative integers is possible for every $k$ is equivalent to the statement that such a collection of positive squares is possible for every $k$, as you can just translate the smallest element to $0$ and get a set of positive squares with one fewer element satisfying the desired property.

Given that nobody has found a set of more than 3 positive squares (and hence no set of more than 4 non-negative integers) with this property, the above method can currently only show that the size of the largest subset of $[1,2,...,N]$ with no square differences is (asymptotically) less than $N/4$.

Answer by Alex Rice for Erdos Conjecture on arithmetic progressions

2010-05-23T11:49:26Z

For those interested, here is the most elementary proof that sets of the natural numbers of positive upper density necessarily have divergent reciprocal sums, r.e. Pete's discussion above.

Suppose $A \subset \mathbf{N}$ and $\displaystyle\limsup_{N \to \infty} \frac{|A\cap [1,N]|}{N} = \alpha > 0$.

Let $N_0=1$, and choose a sequence $N_k$ such that $N_k \geq \frac{4N_{k-1}}{\alpha}$ and $|A \cap [1,N_k)| \geq \frac{\alpha}{2}N_k \text{ }\forall k \in \mathbf{N}$. $$\sum_{n \in A}\frac{1}{n}= \sum_{k=1}^{\infty}\sum_{n \in A\cap [N_{k-1},N_k)}\frac{1}{n} \geq \sum_{k=1}^{\infty}(|A\cap [1,N_k)|-N_{k-1})\frac{1}{N_k}$$ $$ \geq \sum_{k=1}^{\infty}(\frac{\alpha}{2}N_k - \frac{\alpha}{4}N_k) \frac{1}{N_k}=\sum_{k=1}^{\infty}\frac{\alpha}{4} \to \infty.$$ This is really just a generalization of the classical proof of the divergence of the harmonic series, where you group together progressively larger collections of consecutive terms that add to at least one-half. Hope this helps!

Comment by Alex Rice

2011-08-21T21:16:55Z

I realize that this probably should've been a comment as opposed to an "answer". I'm a bit new to this...