In
mathematics
Mathematics is an area of knowledge that includes the topics of numbers, formulas and related structures, shapes and the spaces in which they are contained, and quantities and their changes. These topics are represented in modern mathematics ...
, a square-difference-free set is a
set
Set, The Set, SET or SETS may refer to:
Science, technology, and mathematics Mathematics
*Set (mathematics), a collection of elements
*Category of sets, the category whose objects and morphisms are sets and total functions, respectively
Electro ...
of
natural number
In mathematics, the natural numbers are those numbers used for counting (as in "there are ''six'' coins on the table") and ordering (as in "this is the ''third'' largest city in the country").
Numbers used for counting are called ''Cardinal n ...
s, no two of which differ by a
square number
In mathematics, a square number or perfect square is an integer that is the square (algebra), square of an integer; in other words, it is the multiplication, product of some integer with itself. For example, 9 is a square number, since it equals ...
.
Hillel Furstenberg
Hillel (Harry) Furstenberg ( he, הלל (הארי) פורסטנברג) (born September 29, 1935) is a German-born American-Israeli mathematician and professor emeritus at the Hebrew University of Jerusalem. He is a member of the Israel Academy o ...
and
András Sárközy
András Sárközy (born in Budapest) is a Hungarian mathematician, working in analytic and combinatorial number theory, although his first works were in the fields of geometry and classical analysis. He has the largest number of papers co-auth ...
proved in the late 1970s the Furstenberg–Sárközy theorem of
additive number theory
Additive number theory is the subfield of number theory concerning the study of subsets of integers and their behavior under addition. More abstractly, the field of additive number theory includes the study of abelian groups and commutative semigr ...
showing that, in a certain sense, these sets cannot be very large. In the game of
subtract a square, the positions where the next player loses form a square-difference-free set. Another square-difference-free set is obtained by doubling the
Moser–de Bruijn sequence
In number theory, the Moser–de Bruijn sequence is an integer sequence named after Leo Moser and Nicolaas Govert de Bruijn, consisting of the sums of distinct powers of 4, or equivalently the numbers whose binary representations are nonzero on ...
.
The best known
upper bound
In mathematics, particularly in order theory, an upper bound or majorant of a subset of some preordered set is an element of that is greater than or equal to every element of .
Dually, a lower bound or minorant of is defined to be an element ...
on the size of a square-difference-free set of numbers up to
is only slightly sublinear, but the largest known sets of this form are significantly smaller, of size
. Closing the gap between these upper and lower bounds remains an
open problem In science and mathematics, an open problem or an open question is a known problem which can be accurately stated, and which is assumed to have an objective and verifiable solution, but which has not yet been solved (i.e., no solution for it is know ...
. The sublinear size bounds on square-difference-free sets can be generalized to sets where certain other
polynomial
In mathematics, a polynomial is an expression consisting of indeterminates (also called variables) and coefficients, that involves only the operations of addition, subtraction, multiplication, and positive-integer powers of variables. An exa ...
s are forbidden as differences between pairs of elements.
Example
An example of a set with no square differences arises in the game of
subtract a square, invented by
Richard A. Epstein
Richard Allen Epstein (born April 17, 1943) is an American legal scholar known for his writings on torts, contracts, property rights, law and economics, classical liberalism, and libertarianism. He is the Laurence A. Tisch Professor of Law at ...
and first described in 1966 by
Solomon W. Golomb. In this game, two players take turns removing coins from a pile of coins; the player who removes the last coin wins. In each turn, the player can only remove a nonzero square number of coins from the pile.
[.] Any position in this game can be described by an
integer
An integer is the number zero (), a positive natural number (, , , etc.) or a negative integer with a minus sign (−1, −2, −3, etc.). The negative numbers are the additive inverses of the corresponding positive numbers. In the language ...
, its number of coins.
The non-negative integers can be partitioned into "cold" positions, in which the player who is about to move is losing, and "hot" positions, in which the player who is about to move can win by moving to a cold position. No two cold positions can differ by a square, because if they did then a player faced with the larger of the two positions could move to the smaller position and win. Thus, the cold positions form a set with no square difference:
These positions can be generated by a
greedy algorithm
A greedy algorithm is any algorithm that follows the problem-solving heuristic of making the locally optimal choice at each stage. In many problems, a greedy strategy does not produce an optimal solution, but a greedy heuristic can yield locally ...
in which the cold positions are generated in numerical order, at each step selecting the smallest number that does not have a square difference with any previously selected As Golomb observed, the cold positions are infinite, and more strongly the number of cold positions up to
is at least proportional For, if there were fewer cold positions, there wouldn't be enough of them to supply a winning move to each hot position.
The Furstenberg–Sárközy theorem shows, however, that the cold positions are less frequent than hot positions: for every
, and for all large the proportion of cold positions up to
is That is, when faced with a starting position in the range from the first player can win from most of these positions.
Numerical evidence suggests that the actual number of cold positions is
Upper bounds
According to the Furstenberg–Sárközy theorem, if
is a square-difference-free set, then the
natural density In number theory, natural density (also referred to as asymptotic density or arithmetic density) is one method to measure how "large" a subset of the set of natural numbers is. It relies chiefly on the probability of encountering members of the de ...
of
is zero. That is, for every
, and for all sufficiently large
, the fraction of the numbers up to
that are in
is less than
. Equivalently, every set of natural numbers with positive
upper density In number theory, natural density (also referred to as asymptotic density or arithmetic density) is one method to measure how "large" a subset of the set of natural numbers is. It relies chiefly on the probability of encountering members of the de ...
contains two numbers whose difference is a square, and more strongly contains infinitely many such pairs. The Furstenberg–Sárközy theorem was
conjecture
In mathematics, a conjecture is a conclusion or a proposition that is proffered on a tentative basis without proof. Some conjectures, such as the Riemann hypothesis (still a conjecture) or Fermat's Last Theorem (a conjecture until proven in 19 ...
d by
László Lovász
László Lovász (; born March 9, 1948) is a Hungarian mathematician and professor emeritus at Eötvös Loránd University, best known for his work in combinatorics, for which he was awarded the 2021 Abel Prize jointly with Avi Wigderson. He ...
, and proved independently in the late 1970s by
Hillel Furstenberg
Hillel (Harry) Furstenberg ( he, הלל (הארי) פורסטנברג) (born September 29, 1935) is a German-born American-Israeli mathematician and professor emeritus at the Hebrew University of Jerusalem. He is a member of the Israel Academy o ...
and
András Sárközy
András Sárközy (born in Budapest) is a Hungarian mathematician, working in analytic and combinatorial number theory, although his first works were in the fields of geometry and classical analysis. He has the largest number of papers co-auth ...
, after whom it is named. Since their work, several other proofs of the same result have been published, generally either simplifying the previous proofs or strengthening the bounds on how sparse a square-difference-free set must be.
[.] The best upper bound currently known is due to
Thomas Bloom and
James Maynard, who show that a square-difference-free set can include at most
of the integers from
to
, as expressed in
big O notation
Big ''O'' notation is a mathematical notation that describes the limiting behavior of a function when the argument tends towards a particular value or infinity. Big O is a member of a family of notations invented by Paul Bachmann, Edmund Lan ...
, where
is some absolute constant.
Most of these proofs that establish quantitative upper bounds use
Fourier analysis
In mathematics, Fourier analysis () is the study of the way general functions may be represented or approximated by sums of simpler trigonometric functions. Fourier analysis grew from the study of Fourier series, and is named after Josep ...
or
ergodic theory
Ergodic theory (Greek: ' "work", ' "way") is a branch of mathematics that studies statistical properties of deterministic dynamical systems; it is the study of ergodicity. In this context, statistical properties means properties which are expres ...
, although neither is necessary to prove the weaker result that every square-difference-free set has zero density.
Lower bounds
Paul Erdős
Paul Erdős ( hu, Erdős Pál ; 26 March 1913 – 20 September 1996) was a Hungarian mathematician. He was one of the most prolific mathematicians and producers of mathematical conjectures of the 20th century. pursued and proposed problems in ...
conjectured that every square-difference-free set has
elements up to
, for some constant
, but this was disproved by Sárközy, who proved that denser sequences exist. Sárközy weakened Erdős's conjecture to suggest that, for every
, every square-difference-free set has
elements up to
. This, in turn, was disproved by
Imre Z. Ruzsa, who found square-difference-free sets with up to
elements.
Ruzsa's construction chooses a
square-free {{no footnotes, date=December 2015
In mathematics, a square-free element is an element ''r'' of a unique factorization domain ''R'' that is not divisible by a non-trivial square. This means that every ''s'' such that s^2\mid r is a unit of ''R''.
A ...
integer
as the
radix
In a positional numeral system, the radix or base is the number of unique digits, including the digit zero, used to represent numbers. For example, for the decimal/denary system (the most common system in use today) the radix (base number) is t ...
of the base-
notation for the integers, such that there exists a large set
of numbers from
to
none of whose difference are squares
modulo . He then chooses his square-difference-free set to be the numbers that, in base-
notation, have members of
in their
even
Even may refer to:
General
* Even (given name), a Norwegian male personal name
* Even (surname)
* Even (people), an ethnic group from Siberia and Russian Far East
** Even language, a language spoken by the Evens
* Odd and Even, a solitaire game w ...
digit positions. The digits in
odd
Odd means unpaired, occasional, strange or unusual, or a person who is viewed as eccentric.
Odd may also refer to:
Acronym
* ODD (Text Encoding Initiative) ("One Document Does it all"), an abstracted literate-programming format for describing X ...
positions of these numbers can be arbitrary. Ruzsa found the seven-element set
modulo
, giving the stated bound.
Subsequently, Ruzsa's construction has been improved by using a different base,
, to give square-difference-free sets with size
When applied to the base
, the same construction generates the
Moser–de Bruijn sequence
In number theory, the Moser–de Bruijn sequence is an integer sequence named after Leo Moser and Nicolaas Govert de Bruijn, consisting of the sums of distinct powers of 4, or equivalently the numbers whose binary representations are nonzero on ...
multiplied by two, a square-difference-free set of
elements. This is too sparse to provide nontrivial lower bounds on the Furstenberg–Sárközy theorem but the same sequence has other notable mathematical properties.
Based on these results, it has been conjectured that for every
and every sufficiently large
there exist square-difference-free subsets of the numbers from
to
with
elements. That is, if this conjecture is true, the exponent of one in the upper bounds for the Furstenberg–Sárközy theorem cannot be lowered.
As an alternative possibility, the exponent 3/4 has been identified as "a natural limitation to Ruzsa's construction" and another candidate for the true maximum growth rate of these sets.
Generalization to other polynomials
The upper bound of the Furstenberg–Sárközy theorem can be generalized from sets that avoid square differences to sets that avoid differences in
,
the values at integers of a polynomial
with integer
coefficient
In mathematics, a coefficient is a multiplicative factor in some term of a polynomial, a series, or an expression; it is usually a number, but may be any expression (including variables such as , and ). When the coefficients are themselves var ...
s, as long as the values of
include an integer multiple of every integer.
The condition on multiples of integers is necessary for this result, because if there is an integer
whose multiples do not appear in
, then the multiples of
would form a set of nonzero density with no differences in
.
References
{{DEFAULTSORT:Furstenberg-Sarkozy theorem
Additive number theory