User alex rice - MathOverflow most recent 30 from http://mathoverflow.net 2013-05-18T23:40:36Z http://mathoverflow.net/feeds/user/3632 http://www.creativecommons.org/licenses/by-nc/2.5/rdf http://mathoverflow.net/questions/73346/sequences-of-squares-with-all-square-differences/73359#73359 Answer by Alex Rice for Sequences of Squares with all square differences Alex Rice 2011-08-21T21:12:16Z 2011-08-21T21:12:16Z <p>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)$.</p> <p>In particular, if $S$ is the set of squares, $A \subset [1,2,...,N]$ with $(A-A) \cap S = \emptyset$, and $a_1 &lt; a_2&lt; ... &lt; 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.</p> <p>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.</p> <p>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$.</p> http://mathoverflow.net/questions/13230/erdos-conjecture-on-arithmetic-progressions/25656#25656 Answer by Alex Rice for Erdos Conjecture on arithmetic progressions Alex Rice 2010-05-23T11:49:26Z 2010-05-23T11:49:26Z <p>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.</p> <p>Suppose $A \subset \mathbf{N}$ and $\displaystyle\limsup_{N \to \infty} \frac{|A\cap [1,N]|}{N} = \alpha > 0$. </p> <p>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!</p> http://mathoverflow.net/questions/73346/sequences-of-squares-with-all-square-differences/73359#73359 Comment by Alex Rice Alex Rice 2011-08-21T21:16:55Z 2011-08-21T21:16:55Z I realize that this probably should've been a comment as opposed to an &quot;answer&quot;. I'm a bit new to this...