Furstenberg–Sárközy theorem

The Furstenberg–Sárközy theorem is a result in additive number theory on square-difference-free sets, named after Hillel Furstenberg and András Sárközy. It states that, if is a set of natural numbers with the property that no two numbers in differ by a square number, then the natural density 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. [1]


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 by Solomon W. Golomb. In this game, two players take turns removing coins from a pile of coins, with the goal being to be the person who removes the last coin. In each turn, either player can only remove a square number of coins from the pile. [2]

Any position in this game can be described by an integer, 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:

0, 2, 5, 7, 10, 12, 15, 17, 20, 22, 34, 39, 44, … (sequence A030193 in the OEIS)

These positions can be generated by a greedy algorithm 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 number. [2] [3] As Golomb observed, the cold positions are infinite, and more strongly the number of cold positions up to is at least proportional to . For, if there were fewer cold positions, there wouldn't be enough of them to supply a winning move to each hot position. [2] The Furstenberg–Sárközy theorem shows, however, that the cold positions are less frequent than hot positions: for every , and for all large enough , the proportion of cold positions up to is at most . That is, when faced with a starting position in the range from 1 to , the first player can win from most of these positions. [4]