Square-Difference-Free Sets of Size Omega(n^{0.7334...})
| dc.creator | Beigel, Richard | |
| dc.creator | Gasarch, William | |
| dc.date | 2008-04-30 | |
| dc.date | 2008-05-08 | |
| dc.date.accessioned | 2026-07-07T09:37:30Z | |
| dc.date.available | 2026-07-07T09:37:30Z | |
| dc.description | A set A is square-difference free (henceforth SDF) if there do not exist x,y\in A, x\ne y, such that |x-y| is a square. Let sdf(n) be the size of the largest SDF subset of {1,...,n}. Ruzsa has shown that sdf(n) = Ω(n^{0.5(1+ \log_{65} 7)}) = Ω(n^{0.733077...}) We improve on the lower bound by showing sdf(n) = Ω(n^{0.5(1+ \log_{205} 12)})= Ω(n^{.7443...}) As a corollary we obtain a new lower bound on the quadratic van der Waerden numbers. | |
| dc.description | Fixed important typo: in abstract of paper itself, and on page 3, I had quoted a prior result as being sdf(n) \ge Ω(n^n^{...}) when it should have been sdf(n) \ge Ω(n^{...}) | |
| dc.identifier | https://arxiv.org/abs/0804.4892 | |
| dc.identifier | http://arxiv.org/abs/0804.4892 | |
| dc.identifier.uri | http://salesiana.dossiersoluciones.com/handle/123456789/160478 | |
| dc.subject | Combinatorics | |
| dc.subject | 05D10 | |
| dc.title | Square-Difference-Free Sets of Size Omega(n^{0.7334...}) | |
| dc.type | text |