A note on the number of (k, ℓ)-sum-free sets

Tomasz Schoen Mathematisches Seminar Universität zu Kiel Ludewig-Meyn-Str. 4, 24098 Kiel, Germany

                 tos@numerik.uni-kiel.de

and Department of Discrete Mathematics Adam Mickiewicz University Poznań, Poland

Abstract

A set A ⊆ ℕ is (k, ℓ)-sum-free, for k, ℓ ∈ ℕ, k > ℓ, if it contains no solutions to the equation x_{1} +⋯+x_{k} = y_{1} +⋯+y_{ℓ}. Let ρ = ρ(k −ℓ) be the smallest natural number not dividing k − ℓ, and let r = r_{n}, 0 ≤ r < ρ, be such that r ≡ n (mod ρ). The main result of this note says that if (k − ℓ)/ℓ is small in terms of ρ, then the number of (k, ℓ)-sum-free subsets of [1, n] is equal to (φ(ρ) + φ_{r}(ρ) + o(1))2^{⌊n/ρ⌋}, where φ_{r}(x) denotes the number of positive integers m ≤ r relatively prime to x and φ(x) = φ_{x}(x).

Submitted: February 15, 1999; Accepted: May 23, 2000. 1991 Mathematics Subject Classification: 11B75, 11P99.

A set A of positive integers is (k, ℓ)-sum-free for k, ℓ ∈ ℕ, k > ℓ, if there are no solutions to the equation x_{1} + ⋯ + x_{k} = y_{1} + ⋯ + y_{ℓ} in A. Denote by SF_{k,ℓ}^{n} the number of (k, ℓ)-sum-free subsets of [1, n]. Since the set of odd numbers is (2, 1)-sum-free we have SF_{2,1}^{n} ≥ 2^{⌊(n+1)/2⌋}. In fact Erdős and Cameron [6] conjectured SF_{2,1}^{n} = O(2^{n/2}). This conjecture is still open and the best upper bounds for SF_{2,1}^{n} given independently by Alon [1] and Calkin [3], say that, for ℓ ≥ 1,

SF_{ℓ+1,ℓ}^{n} ≤ SF_{2,1}^{n} = O(2^{n/2+o(n)}) .

For ℓ ≥ 3 this bound was recently improved by Bilu [2] who proved that in this case SF_{ℓ+1,ℓ}^{n} = (1 + o(1))2^{⌊(n+1)/2⌋}.

The case of k being much larger than ℓ was treated by Calkin and Taylor [4]. They showed that for some constant c_{k} the number of (k, 1)-sum-free subsets of [1, n] is at most c_{k}2^{\frac{k−1}{k} n}, provided k ≥ 3. Furthermore, Calkin and Thomson proved [5] that for every k and ℓ with k ≥ 4ℓ − 1

SF_{k,ℓ}^{n} ≤ c_{k}2^{(k−ℓ)n/k}.

In order to study the behaviour of SF_{k,ℓ}^{n} let us observe first that there are two natural examples of large (k, ℓ)-sum-free subsets of the interval [1, n]:

{⌊ℓn/k⌋ + 1, …, n}

and

{m ∈ {1, 2, …, n} : m ≡ r (mod ρ)} ,

where gcd(r, ρ) = 1 and ρ = ρ(k − ℓ) = min{s ∈ ℕ : s does not divide k − ℓ}. Thus,

SF_{k,ℓ}^{n} ≥ max (2^{⌊n/ρ⌋}, 2^{⌈(k−ℓ)n/k⌉}).

In this note we study the case k < \frac{ρ}{ρ−1}ℓ so that 2^{⌊n/ρ⌋} > 2^{⌈(k−ℓ)n/k⌉}, and we may expect SF_{k,ℓ}^{n} to be close to 2^{⌊n/ρ⌋}. Indeed, we will prove as our main result that for fixed k and ℓ there exists a bounded function ξ = ξ(n) such that

SF_{k,ℓ}^{n} = (ξ + o(1))2^{⌊n/ρ⌋}

provided k < (1 − \frac{c−1}{cρ−1})\frac{ρ}{ρ−1}ℓ, where c = \frac{1+ln 2}{2 ln 2}, and ℓ is sufficiently large.

For every natural numbers x, r let φ_{r}(x) be the number of positive integers m ≤ r relatively prime to x and let φ(x) abbreviate φ_{x}(x). For a finite set A of integers A define:

d(A) = gcd(A),  d′(A) = d(A − A),
Λ(A) = maxA − minA, Λ′(A) = Λ(A)/d′(A).

Furthermore, let

κ(A) = \frac{Λ′(A) − 1}{|A| − 2}, θ(A) = \frac{max(A)}{Λ(A)},

T (A) = (|A| − 2)(⌊κ(A)⌋ + 1 − κ(A)) + 1

and

hA = {a_{1} + ⋯ + a_{h} : a_{1}, …, a_{h} ∈ A}.

For a specified set A, we simply write d, d′, Λ, etc.

Our approach is based on a remarkable result of Lev [7]. Using an affine transformation of variables his theorem can be stated as follows.

Theorem 1. Let A be a finite set of integers and let h be a positive integer satisfying h > 2κ − 1. Then there exists an integer s such that

{sd′, …, (s + t)d′} ⊆ hA ,

for t = (h − 2⌊κ⌋)Λ′ + 2⌊κ⌋T.

Lemma 1. Let A be a finite set of integers and let h be a positive integer satisfying h > 2κ − 1. Then {0, d′, …, td′} ⊆ hA − hA, where t ≥ (h + 1 − 2κ)Λ′. Proof. Theorem 1 implies that hA contains t = (h − 2⌊κ⌋)Λ′ + 2⌊κ⌋T + 1 consecutive multiples of d′, so that

{0, …, td′} ⊆ hA − hA.

Furthermore,

t = (h−2⌊κ⌋)Λ′ +2⌊κ⌋T = (h+2−2κ−τ)Λ′ + \frac{2⌊κ⌋(κ − ⌊κ⌋) + 2⌊κ⌋(κ − 1)}{κ},

where

τ = \frac{2(κ − ⌊κ⌋)(⌊κ⌋ + 1 − κ)}{κ}.

Since τ ≤ 1 and κ ≥ 1, the result follows. □

Lemma 2. Let A ⊆ [1, n] be a (k, ℓ)-sum-free set, and let r be the residue class mod d′ containing A. Assume that either

d′ < ρ,  (1)

or

(k − ℓ)r ≡ 0 (mod d′).  (2)

Then

κ ≥ \frac{k + 1 − (k − ℓ)θ}{2}.  (3)

Proof. We may assume that ℓ > 2κ − 1, otherwise the assertion is obvious. By Lemma 1 we have

{0, d′, …, td′} ⊆ ℓA − ℓA,

where t ≥ (ℓ + 1 − 2κ)Λ′. Put m = min A. Then any of the assumptions (1),

(2) implies d′|(k − ℓ)m. Since A is a (k, ℓ)-sum-free set, it follows that

(k − ℓ)m > td′ ≥ (ℓ + 1 − 2κ)Λ,

which gives the required inequality. □

Theorem 2. Assume that k > ℓ ≥ 3 are positive integers satisfying

\frac{k − ℓ}{2} · max_{2≤x≤ \frac{ℓ+1}{2}} \frac{\frac{ln x}{x} + \frac{x−1}{x} ln \frac{x}{x−1}}{\frac{k+1}{2} − x} < \frac{ln 2}{ρ}.  (4)

Then

SF_{k,ℓ}^{n} = (φ + φ_{r} + o(1))2^{⌊n/ρ⌋},  (5)

where 0 ≤ r < ρ and r ≡ n (mod ρ). Proof. In order to obtain the lower bound let us observe that there are exactly φ maximal (k, ℓ)-sum-free arithmetic progressions with the difference ρ. Precisely φ_{r} of them have length ⌈n/ρ⌉ and φ − φ_{r} are of length ⌊n/ρ⌋. Since these progressions are pairwise disjoint, there are at least

(φ + φ_{r})2^{⌊n/ρ⌋}

(k, ℓ)-sum-free subsets of [1, n].

Now we estimate SF_{k,ℓ}^{n} from above. First consider (k, ℓ)-sum-free sets satisfying neither (1), nor (2). Plainly each of these is contained in a residue class r mod d′, where d′ ≥ ρ and (k − ℓ)r ≢ 0 mod d′. If d′ = ρ, by the same argument as above, exactly (φ + φ_{r})2^{⌊n/ρ⌋} (k, ℓ)-sum-free subsets of [1, n] are contained in arithmetic progression r mod ρ, where (k − ℓ)r ≢ 0 mod ρ. If d′ > ρ then every progression r mod d′ consists of at most ⌈n/(ρ + 1)⌉ elements hence it contains no more than 2^{⌈n/(ρ+1)⌉} subsets. Furthermore we have less than n^{2} possible choices for the pair (d′, ρ), hence there are at most 2n^{2}2^{n/(ρ+1)} such (k, ℓ)-sum-free sets. Thus, the number of (k, ℓ)-sum-free sets satisfying neither (1), nor (2) does not exceed

(φ + φ_{r})2^{⌊n/ρ⌋} + 2n^{2}2^{n/(ρ+1)}.

To complete the proof it is sufficient to show that the number of (k, ℓ)- sum-free subsets of [1, n] satisfying either (1) or (2) is o(2^{n/ρ}). Denote by B the set of all such subsets, and let

B(K, L, M) = {A ∈ B : |A| = K, Λ(A) = L, max A = M},

so that

B = ⋃_{1≤K≤L+1≤M≤n} B(K, L, M).

We will prove that

max_{1≤K≤L+1≤M≤n} |B(K, L, M)| ≤ e^{μn+O(ln n)},  (6)

where μ is the left-hand side of (4) which in turn implies that

|B| = o(2^{n/ρ}).  (7)

Let us define the following decreasing function x(t) = (k +1−(k −ℓ)t)/2. Note that x(1) = (ℓ + 1)/2, x(t_{2}) = 2 and x(t_{1}) = 1, where

t_{2} = \frac{k − 3}{k − ℓ} ≥ 1 and t_{1} = \frac{k − 1}{k − ℓ}.

Furthermore, put

H(x) = \frac{ln x}{x} + \frac{x − 1}{x} ln \frac{x}{x − 1}.

Observe that H is increasing on (1, 2] and decreasing on [2, ∞). Moreover

μ = max_{1≤t≤t_{2}} \frac{H(x(t))}{t}

and

max_{x≥x(t)^{1≤t≤t_{1}}} \frac{H(x)}{t} = μ.  (8)

Indeed, if 1 ≤ t ≤ t_{2} then x ≥ x(t) ≥ 2 and H(x)/t ≤ H(x(t))/t ≤ μ. If t_{2} ≤ t ≤ t_{1} then H(x)/t ≤ H(2)/t_{2} = H(x(t_{2}))/t_{2} ≤ μ.

Now we are ready to prove (7). For a fixed triple K, L, M with 1 ≤ K ≤ L + 1 ≤ M ≤ n put

θ = \frac{M}{L} , κ = \frac{L − 1}{K − 2}.

Then κ(A) ≤ κ and θ(A) = θ for any A ∈ B(K, L, M). By Lemma 2 we have κ ≥ x(θ). Since κ ≥ 1 by definition, we infer that H(κ)/θ ≤ μ by (8). Using Stirling’s formula we obtain

|B(K, L, M)| ≤ \binom{L − 1}{K − 2}
= exp(H(κ)L + O(ln L))
= exp (\frac{H(κ)}{θ}M + O(ln n))
≤ exp(μn + O(ln n)).

Thus

|B| ≤ n^{3} exp(μn + O(ln n)),

which completes the proof of Theorem 2. □

Corollary 1. The estimate (5) holds, provided k > ℓ ≥ 3 and

\frac{max (\frac{1+ln 2}{2}(k − ℓ), 2(1 + ln \frac{ℓ+1}{2}))}{ℓ + 1} < \frac{ln 2}{ρ}.  (9)

Proof. We need to show that the left-hand side of (4) is not larger than the left-hand side of (9). Since ln(1 + u) ≤ u for u ≥ 0, we have

\frac{x − 1}{x} ln \frac{x}{x − 1} ≤ \frac{1}{x}

for x ≥ 1, so that

μ ≤ \frac{k − l}{2} max_{2≤x≤ \frac{ℓ+1}{2}} \frac{1 + ln x}{x(\frac{k+1}{2} − x)}.  (10)

Furthermore,

max_{2≤x≤ \frac{k−ℓ}{2}} \frac{1 + ln x}{x(\frac{k+1}{2} − x)} ≤ \frac{2}{ℓ + 1} max_{2≤x≤ \frac{ℓ+1}{2}} \frac{1 + ln x}{x} = \frac{1 + ln 2}{ℓ + 1},

max_{\frac{k−ℓ}{2} ≤x≤ \frac{ℓ+1}{2}} \frac{1 + ln x}{x(\frac{k+1}{2} − x)} ≤ \frac{1 + ln \frac{ℓ+1}{2}}{min_{\frac{k−ℓ}{2} ≤x≤ \frac{ℓ+1}{2}} x(\frac{k+1}{2} − x)} = 4\frac{1 + ln \frac{ℓ+1}{2}}{(k − ℓ)(ℓ + 1)}.

Combining the above inequalities with (10), the result follows. □

Let us conclude this note with some further remarks on the range of k and ℓ satisfying (4). If \frac{1+ln 2}{2}(k −ℓ) ≤ 2(1+ln \frac{ℓ+1}{2}), that is (k −ℓ) ≤ \frac{4}{1+ln 2}(1+

ln \frac{ℓ+1}{2}), then by Corollary 1 (4) holds, provided ℓ ≥ \frac{2}{ln 2}(1 + ln \frac{ℓ+1}{2})ρ(k − ℓ). By the prime number theorem, ρ(n) ≤ (1 + o(1)) ln n, hence the inequality ℓ ≥ \frac{2}{ln 2}(1+ln \frac{ℓ+1}{2})ρ(k−ℓ) is fulfilled for every sufficiently large ℓ. If \frac{1+ln 2}{2}(k−

ℓ) ≥ 2(1 + ln \frac{ℓ+1}{2}) then (4) holds for every k and ℓ such that ℓ < k < \frac{cρ}{cρ−1}ℓ = (1 − \frac{c−1}{cρ−1})\frac{ρ}{ρ−1}ℓ, where c = \frac{1+ln 2}{2 ln 2}. Thus, from Theorem 2, one can deduce that there exists an absolute constant ℓ_{0} such that

SF_{k,ℓ}^{n} = (φ + φ_{r} + o(1))2^{⌊n/ρ⌋},

provided ℓ_{0} < ℓ < k < (1 − \frac{c−1}{cρ−1})\frac{ρ}{ρ−1}ℓ.

Acknowledgments. I would like to thank referees for many valuable comments. Due to their suggestions we were able to prove the main result of the note in its present sharp form.

References

[1] N. Alon, Independent sets in regular graphs and sum-free sets of finite groups, Israel J. Math. 73 (1991), 247–256.

[2] Yu. Bilu, Sum-free sets and related sets, Combinatorica 18 (1998), 449– 459.

[3] N. J. Calkin, On the number of sum-free sets, Bull. Lond. Math. Soc. 22 (1990), 141–144.

[4] N. J. Calkin, A. C. Taylor: Counting sets of integers, no k of which sum to another, J. Number Theory 57 (1996), 323–327.

[5] N. J. Calkin, J. M. Thomson, Counting generalized sum-free sets, J. Number Theory 68 (1998), 151–160.

[6] P. J. Cameron, P. Erdős, On the number of sets of integers with various properties, in R. A. Mollin (ed.), Number Theory: Proc. First Conf. Can. Number Th. Ass., Banff, 1988, de Gruyter, 1990, 61–79.

[7] V. F. Lev, Optimal representation by sumsets and subset sums, J. Number Theory 62 (1997), 127–143.