An improved lower bound related to the Furstenberg-Sárközy theorem

MaRDI QIDQ2256129zbMATH OpenFDO

Authors Mark Lewko

Publication date 19 February 2015

Published in The Electronic Journal of Combinatorics (Search for Journal in Brave)

Full work available at URL http://www.combinatorics.org/ojs/index.php/eljc/article/view/v22i1p32

IPFS File on IPFS (Hint: this is only the Hash - if you get a timeout, this file is not available on our server.)

zbMATH Keywords

difference setRamsey theorysquares

Mathematics Subject Classification ID

Combinatorial aspects of difference sets (number-theoretic, group-theoretic, etc.) (05B10) Ramsey theory (05D10)

Review text

Summary: Let \(D(n)\) denote the cardinality of the largest subset of the set \(\{1,2,\dots,n\}\) such that the difference of no pair of distinct elements is a square. A well-known theorem of Furstenberg and Sárközy states that \(D(n)=o(n)\). In the other direction, \textit{I. Z. Ruzsa} [Period. Math. Hung. 15, 205--209 (1984; Zbl 0552.10035)] has proven that \(D(n) \gtrsim n^{\gamma}\) for \(\gamma = \frac{1}{2}\left( 1 + \frac{\log 7}{\log 65} \right) \approx 0.733077\). We improve this to \(\gamma = \frac{1}{2}\left( 1 + \frac{\log 12}{\log 205} \right) ~\approx 0.733412\).

Recommendations

• A new upper bound for sets with no square differences
• A new proof of Sárközy's theorem
• scientific article; zbMATH DE number 3952888
• Difference sets without squares
• Sárközy's theorem for P-intersective polynomials

Cites work

• A new proof of Sárközy's theorem
• A note on Elkin's improvement of Behrend's construction
• A quantitative improvement for Roth's theorem on arithmetic progressions: Table 1.
• An improved branch and bound algorithm for the maximum clique problem
• Difference sets without squares
• Ergodic behavior of diagonal measures and a theorem of Szemeredi on arithmetic progressions
• scientific article; zbMATH DE number 3641575 (Why is no real title available?)
• On difference sets of sequences of integers. I
• On difference sets of sequences of integers. III
• On Maximal Residue Difference Sets Modulo p
• On Quadratic Residues and Nonresidues in Difference Sets Modulo m
• On Roth's theorem on progressions
• On Sets of Integers Which Contain No Three Terms in Arithmetical Progression
• On Sets of Natural Numbers Whose Difference Set Contains No Squares

Cited in

(18)

• New lower bounds for the Hadwiger numbers of \(\ell_p\) balls for \(p<2\)
• An improved probability bound for the approximate S-lemma
• A new proof of Sárközy's theorem
• Asymptotic improvements to the lower bound of certain bipartite Turán numbers
• An Improved Bound for an Extension of Fine and Wilf’s Theorem and Its Optimality
• Faster evaluation of subtraction games
• Multivariate polynomial values in difference sets
• scientific article; zbMATH DE number 3952888 (Why is no real title available?)
• A maximal extension of the best-known bounds for the Furstenberg-Sárközy theorem
• scientific article; zbMATH DE number 6169011 (Why is no real title available?)
• Sets whose differences avoid squares modulo m
• A new upper bound for sets with no square differences
• The Lower Bound for Koldobsky’s Slicing Inequality via Random Rounding
• Near optimal bounds in Freiman's theorem
• Automata, Languages and Programming
• A strong-type Furstenberg-Sárközy theorem for sets of positive measure
• An improved bound for the Manickam-Miklós-Singhi conjecture
• The Furstenberg-Sárközy theorem for polynomials in one or more prime variables

Describes a project that uses

Uses Software

• MaxCliqueDyn

This page was built for publication: An improved lower bound related to the Furstenberg-Sárközy theorem

Report a bug (only for logged in users!)Click here to report a bug for this page (MaRDI item Q2256129)