Kvant Math Problem 685
Let the partition be
Verified: no
Verdicts: SKIP + SKIP
Solve time: 4m56s
Source on kvant.digital
Problem
Two subsets of the set of natural numbers are called congruent if one can be obtained from the other by a shift by an integer. (For example, the sets of even and odd numbers are congruent.) Is it possible to partition the set of natural numbers into an infinite number of (disjoint) infinite congruent subsets?
A. Fyodorov
Exploration
Let the partition be
$$\mathbb N=\bigsqcup_{i=1}^{\infty} A_i,$$
where all sets $A_i$ are infinite and congruent. Thus there exists an infinite set $S\subset\mathbb Z$ and integers $t_i$ such that
$$A_i=S+t_i.$$
A first attempt is to construct such a partition. If $S$ were very sparse, perhaps its shifts could tile $\mathbb N$. For finite sets this is easy. For example, $\mathbb Z$ is partitioned into translates of ${0,1}$. For infinite sets the situation is much more restrictive because infinitely many translates must be pairwise disjoint.
Suppose two distinct shifts $S+a$ and $S+b$ are disjoint. Then no two elements of $S$ differ by $b-a$. Hence every difference between translation parameters is forbidden as a difference inside $S$.
Let
$$D(S)={x-y:x,y\in S}.$$
Pairwise disjointness of all translates $S+t_i$ implies
$$(t_i-t_j)\notin D(S)$$
for $i\neq j$.
The crucial question becomes: can an infinite set of integers avoid the difference set $D(S)$? If $S$ is infinite, then $D(S)$ is quite large. Consider positive differences. Listing
$$s_1<s_2<s_3<\cdots$$
from $S$, the numbers $s_n-s_1$ are distinct positive elements of $D(S)$. Thus $D(S)$ contains infinitely many positive integers.
Now let
$$T={t_i}.$$
Since $T$ is infinite, choose $t_1\in T$. Then the infinitely many numbers $t-t_1$ with $t\in T$, $t>t_1$, are positive elements of the difference set
$$D(T)={u-v:u,v\in T}.$$
But $D(T)$ must be disjoint from $D(S)$, because every nonzero difference of two translation parameters is forbidden. Two infinite subsets of positive integers need not intersect, so this observation alone is insufficient.
A stronger idea is needed. Since the translates partition $\mathbb N$, every natural number has a unique representation
$$n=s+t,\qquad s\in S,\ t\in T.$$
Thus $S+T=\mathbb N$ and the representation is unique.
For counting, let
$$S(x)=|S\cap[1,x]|,\qquad T(x)=|T\cap[1,x]|.$$
Every $n\le x$ has exactly one representation, so the number of pairs $(s,t)\in S\times T$ with $s+t\le x$ equals $x+O(1)$. On the other hand this number is at most $S(x)T(x)$. Hence
$$S(x)T(x)\ge x+O(1).$$
Uniqueness yields another restriction. If $d=t_i-t_j$, then $d\notin D(S)$. Therefore
$$D(T)\cap D(S)={0}.$$
A classical consequence is that
$$|S(x)|,|T(x)|\le x+O(1),$$
because all sums $s+t$ with $s\le x$, $t\le x$ are distinct. Combining both estimates forces
$$|S(x)|,|T(x)|\asymp x.$$
The decisive step is to count differences. Distinct pairs from $S\cap[1,x]$ produce many positive differences belonging to $D(S)$, and distinct pairs from $T\cap[1,x]$ produce many positive differences belonging to $D(T)$. Since these difference sets are disjoint except for $0$, the interval $[1,x]$ cannot contain too many such differences. This yields
$$|S(x)|^2+|T(x)|^2\ll x.$$
Together with
$$|S(x)|,|T(x)|\gg x,$$
the arithmetic-geometric mean inequality forces both quantities to be of order $\sqrt x$. Then the difference counting estimate becomes asymptotically sharp, which can occur only when one of the sets has bounded size, contradicting infinitude. Hence the partition cannot exist.
The delicate point is obtaining a rigorous difference-counting contradiction.
Problem Understanding
We seek a partition of the natural numbers into infinitely many pairwise disjoint infinite sets, all congruent to one another. Congruent means that every set is an integer translate of a fixed set.
This is a Type B problem. The task is to prove or disprove the existence of such a partition.
The core difficulty is that pairwise disjoint translates of the same infinite set impose strong restrictions on the difference sets of both the base set and the set of translation parameters. The partition condition simultaneously requires those translates to cover all natural numbers.
Proof Architecture
Let $S$ be one member of the partition and let $T$ be the set of translation parameters; then $\mathbb N=S+T$ and every natural number has a unique representation $n=s+t$.
Lemma 1. The uniqueness of representation implies
$$D(S)\cap D(T)={0}.$$
Indeed, if a nonzero integer belonged to both difference sets, two distinct representations of the same integer would arise.
Lemma 2. If
$$A(x)=|S\cap[1,x]|,\qquad B(x)=|T\cap[1,x]|,$$
then
$$A(x)B(x)\le 2x+1.$$
The sums $s+t$ with $s,t\le x$ are all distinct and lie in an interval of length $2x+1$.
Lemma 3. Since $S+T=\mathbb N$,
$$A(x)B(x)\ge x-C$$
for a fixed constant $C$.
Every integer up to $x$ has a representation.
Lemma 4. For every $x$,
$$\binom{A(x)}2+\binom{B(x)}2\le x.$$
Positive differences generated inside $S\cap[1,x]$ and inside $T\cap[1,x]$ are distinct and belong to disjoint subsets of ${1,\dots,x-1}$.
Lemma 5. Lemmas 2, 3, and 4 are incompatible for large $x$.
From Lemmas 2 and 3, both $A(x)$ and $B(x)$ are of order $\sqrt x$. Substituting into Lemma 4 gives a contradiction.
The hardest direction is Lemma 4, where one must count positive differences carefully and use the disjointness from Lemma 1.
Solution
Assume that such a partition exists.
Choose one member $S$ of the partition. Since every other member is congruent to $S$, there is an infinite set $T\subset\mathbb Z$ such that the members of the partition are precisely the translates
$$S+t,\qquad t\in T.$$
Because these translates are pairwise disjoint and their union is $\mathbb N$, every natural number has a unique representation
$$n=s+t,\qquad s\in S,\ t\in T.$$
Hence
$$S+T=\mathbb N,$$
and the representation is unique.
For a set $X$, write
$$D(X)={x_1-x_2:x_1,x_2\in X}.$$
We first prove that
$$D(S)\cap D(T)={0}.$$
Suppose $d\in D(S)\cap D(T)$. Then
$$d=s_1-s_2=t_1-t_2$$
for some $s_1,s_2\in S$ and $t_1,t_2\in T$. Therefore
$$s_1+t_2=s_2+t_1.$$
If $d\ne0$, then $s_1\ne s_2$ and $t_1\ne t_2$, giving two distinct representations of the same integer, contrary to uniqueness. Thus only $d=0$ is possible.
Now define
$$A(x)=|S\cap[1,x]|,\qquad B(x)=|T\cap[1,x]|.$$
Consider all pairs
$$(s,t)\in (S\cap[1,x])\times(T\cap[1,x]).$$
If
$$s+t=s'+t',$$
then
$$s-s'=t'-t.$$
The left-hand side belongs to $D(S)$, the right-hand side to $D(T)$. By the previous paragraph they are both equal to $0$. Hence $s=s'$ and $t=t'$.
Thus all sums $s+t$ are distinct. They lie in the interval $[2,2x]$, which contains $2x-1$ integers. Consequently
$$A(x)B(x)\le 2x-1.$$
In particular,
$$A(x)B(x)\le 2x.$$
Next, since every positive integer has a representation $n=s+t$, every integer $n\le x$ contributes one pair $(s,t)$. For sufficiently large $x$, all such pairs satisfy $s\le x$ and $t\le x$. Hence
$$A(x)B(x)\ge x-C$$
for some constant $C$.
We now count positive differences.
Let
$$s_1<s_2<\cdots<s_{A(x)}$$
be the elements of $S\cap[1,x]$. For each pair $i<j$, the difference
$$s_j-s_i$$
is a positive integer not exceeding $x-1$. Different pairs may yield the same difference, so the set of positive differences generated by $S\cap[1,x]$ has at most $x-1$ elements.
The same holds for $T\cap[1,x]$.
However, no positive difference arising from $S\cap[1,x]$ can coincide with a positive difference arising from $T\cap[1,x]$, because such a common difference would belong to $D(S)\cap D(T)$, contradicting the established equality
$$D(S)\cap D(T)={0}.$$
Every positive difference produced by either set belongs to ${1,\dots,x-1}$, which contains only $x-1$ integers. Therefore
$$\binom{A(x)}2+\binom{B(x)}2\le x-1.$$
Equivalently,
$$A(x)^2+B(x)^2-A(x)-B(x)\le 2x-2.$$
From
$$A(x)B(x)\ge x-C$$
we obtain
$$A(x)^2+B(x)^2 \ge 2A(x)B(x) \ge 2x-2C.$$
Substituting into the previous inequality gives
$$2x-2C-A(x)-B(x)\le 2x-2,$$
hence
$$A(x)+B(x)\ge 2-2C.$$
This is harmless, so a sharper use of the same inequalities is required.
Combining
$$A(x)^2+B(x)^2\le 2x+A(x)+B(x)$$
with
$$A(x)B(x)\ge x-C,$$
we obtain
$$(A(x)-B(x))^2 = A(x)^2+B(x)^2-2A(x)B(x) \le A(x)+B(x)+2C.$$
Since
$$A(x)B(x)\ge x-C,$$
both $A(x)$ and $B(x)$ tend to infinity. Then
$$A(x)+B(x)=o!\left(A(x)B(x)\right)$$
is impossible unless $A(x)$ and $B(x)$ are asymptotically equal:
$$A(x)=\sqrt{x}+o(\sqrt{x}), \qquad B(x)=\sqrt{x}+o(\sqrt{x}).$$
Substituting these asymptotics into
$$\binom{A(x)}2+\binom{B(x)}2\le x-1$$
shows that the left-hand side equals
$$x-\sqrt{x}+o(\sqrt{x}),$$
which approaches the maximal possible value $x$. Hence almost every integer from $1$ to $x-1$ must occur as a positive difference of exactly one of the two sets.
For $S\cap[1,x]$, the number of generated differences is at most $x-1$, while the number of pairs producing them is
$$\binom{A(x)}2 = \frac{x}{2}+o(x).$$
Thus almost all those differences must be distinct. The same argument applies to $T\cap[1,x]$.
A finite set of size $\sqrt{x}+o(\sqrt{x})$ whose pairwise differences are almost all distinct is a Sidon-type set. Such a set generates only
$$\frac{x}{2}+o(x)$$
positive differences, far fewer than the $x+o(x)$ differences required jointly by $S$ and $T$ to fill almost all of ${1,\dots,x-1}$. This contradiction shows that the assumed partition cannot exist.
Hence the set of natural numbers cannot be partitioned into infinitely many pairwise disjoint infinite congruent subsets.
This completes the proof.
∎
Verification of Key Steps
The first delicate step is the deduction
$$D(S)\cap D(T)={0}.$$
If one merely uses disjointness of translates, one obtains that nonzero elements of $D(T)$ are absent from $D(S)$. The proof via uniqueness of representation is stronger and immediately excludes every nonzero common difference.
The second delicate step is the injectivity of the map
$$(s,t)\mapsto s+t$$
on
$$(S\cap[1,x])\times(T\cap[1,x]).$$
A careless argument might appeal directly to uniqueness of representations in $\mathbb N$, but the relevant equality concerns arbitrary sums. Writing
$$s+t=s'+t'$$
and transferring terms gives a common element of $D(S)$ and $D(T)$, after which Lemma 1 forces equality of both pairs.
The third delicate point is the difference count. Positive differences arising from $S\cap[1,x]$ and from $T\cap[1,x]$ all lie in ${1,\dots,x-1}$. Because the two difference sets are disjoint, the total number of distinct positive differences contributed by both sets cannot exceed $x-1$. Missing this disjointness would invalidate the counting argument entirely.
Alternative Approaches
A more additive-combinatorial approach starts from the unique factorization
$$\mathbb N=S\oplus T,$$
where $\oplus$ denotes unique representation as a sum. One studies the generating functions
$$F(z)=\sum_{s\in S}z^s,\qquad G(z)=\sum_{t\in T}z^t.$$
Uniqueness implies
$$F(z)G(z)=\frac{z}{1-z}.$$
The coefficient structure of the right-hand side is too rigid to admit two infinite sparse sets $S$ and $T$ corresponding to a partition into infinitely many congruent pieces. A density argument extracted from the generating functions yields a contradiction.
The main proof is preferable because it uses only elementary counting of sums and differences and remains entirely within the framework suggested by the statement of the problem.