In
mathematics
Mathematics is a field of study that discovers and organizes methods, Mathematical theory, theories and theorems that are developed and Mathematical proof, proved for the needs of empirical sciences and mathematics itself. There are many ar ...
, 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 the numbers 0, 1, 2, 3, and so on, possibly excluding 0. Some start counting with 0, defining the natural numbers as the non-negative integers , while others start with 1, defining them as the positive in ...
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 (; 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 of Sciences and Humanities and U.S. Natio ...
and
András Sárközy 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 semigro ...
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.
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 every element of .
Dually, a lower bound or minorant of is defined to be an element of that is less ...
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 kno ...
. The sublinear size bounds on square-difference-free sets can be generalized to sets where certain other
polynomial
In mathematics, a polynomial is a Expression (mathematics), mathematical expression consisting of indeterminate (variable), indeterminates (also called variable (mathematics), variables) and coefficients, that involves only the operations of addit ...
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 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 (0), a positive natural number (1, 2, 3, ...), or the negation of a positive natural number (−1, −2, −3, ...). The negations or additive inverses of the positive natural numbers are referred to as negative in ...
, 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 desi ...
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 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 or Fermat's conjecture (now a theorem, proven in 1995 by Andrew Wiles), ha ...
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 (; 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 of Sciences and Humanities and U.S. Natio ...
and
András Sárközy, 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 asymptotic analysis, limiting behavior of a function (mathematics), function when the Argument of a function, argument tends towards a particular value or infinity. Big O is a memb ...
, 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 Joseph Fo ...
or
ergodic theory
Ergodic theory is a branch of mathematics that studies statistical properties of deterministic dynamical systems; it is the study of ergodicity. In this context, "statistical properties" refers to properties which are expressed through the behav ...
, 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 ( ; 26March 191320September 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 discrete mathematics, g ...
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''.
...
integer
as the
radix
In a positional numeral system, the radix (radices) or base is the number of unique digits, including the digit zero, used to represent numbers. For example, for the decimal system (the most common system in use today) the radix is ten, becaus ...
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
In computing and mathematics, the modulo operation returns the remainder or signed remainder of a division, after one number is divided by another, the latter being called the '' modulus'' of the operation.
Given two positive numbers and , mo ...
. He then chooses his square-difference-free set to be the numbers that, in base-
notation, have members of
in their
even digit positions. The digits in
odd 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 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 Factor (arithmetic), multiplicative factor involved in some Summand, term of a polynomial, a series (mathematics), series, or any other type of expression (mathematics), expression. It may be a Dimensionless qu ...
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
Unsolved problems in number theory