B_{h}[g] SEQUENCES

Javier Cilleruelo and Jorge Jiménez-Urroz

Abstract. We give new upper and lower bounds for F_{h}(g, N), the maximum size of a B_{h}[g] sequence contained in [1, N]. We prove

F_{h}(g, N) ≤ (\sqrt{3h}h!gN)^{1/h},

and for any ϵ > 0 and g > g(ϵ, h),

F_{h}(g, N) ≥ ((1 − ϵ)\sqrt{\frac{π}{6}} \sqrt{h}gN)^{1/h} + o(N^{1/h}).

1. Introduction

Given a sequence of integers A, we define R_{h}(A; k) as the number of representations of k as the sum of h elements of A,

R_{h}(A; k) = #{k = a_{1} + ⋯ + a_{h}; a_{1} ≤ ⋯ ≤ a_{h}, a_{i} ∈ A},

and we say that a sequence of integers A is a B_{h}[g] sequence if R_{h}(A; k) ≤ g for any integer k. Sidon was led to consider such sequences in connection with the theory of Fourier series. B_{2}[1] sequences are also called Sidon sequences.

It is a major problem giving good estimates for F_{h}(g, N), the maximum size of B_{h}[g] sequences contained in {1, …, N}. See [H-R] for a classical reference about this topic, and [S-S] and [K] for recent surveys.

By a trivial counting argument we obtain the upper bound

F_{h}(g, N) ≤ (hh!gN)^{1/h}.

For g = 1, Erdős and Turan [E-T] proved F_{2}(1, N) ≤ N^{1/2} +O(N^{1/4}). See [C1] for new upper bounds for F_{h}(1, N), h ≥ 3.

Typeset by AMS-TEX

1991 Mathematics Subject Classification. 11B13.

Key words and phrases. B_{h} sequences, Sidon sets.

On the other hand, Erdős observed in an addendum to [E-T] that a construction of J. Singer in [S] gives F_{2}(1, N) ≥ N^{1/2} + o(N^{1/2}). (See [R] for an easy construction). Later R. C. Bose and S. Chowla [B-Ch] were able to prove F_{h}(1, N) ≥ N^{1/h} + o(N^{1/h}) for any integer h.

When g > 1 is more difficult to obtain good estimates for F_{h}(g, N). The first author [C2] and M. Helm [H], independently proved F_{2}(2, N) ≤ \sqrt{6N} + 1. In [C-R-T] nontrivial upper bounds were proved for F_{h}(g, N):

F_{2}(g, N) ≤ (\frac{4}{1 + \frac{1}{(π/2+1)^{2}}} gN)^{1/2} + o(N^{1/2}),

F_{h}(g, N) ≤ \frac{1}{(1 + cos^{h}(π/h))^{1/h}} (hh!gN)^{1/h} + o(N^{1/h}), h ≥ 3.

Also N. Alon (see [K]) has obtained non trivial upper bounds for large h by exploiting the “concentration” of the sums a_{1} + ⋯ + a_{h} around their mean, using the Chebyshev inequality. He gets

F_{h}(g, N) ≤ (3^{3/2}\sqrt{h}h!gN)^{1/h} + o(N^{1/h}).

In section 2 we get new upper bounds which improve the previous ones for h ≥ 7. In particular we prove

Theorem 1.1.

F_{h}(g, N) ≤ (\sqrt{3h}h!gN)^{1/h}.

In relation to the lower bounds, a construction of M. Kolountzakis [K] of B_{2}[2] sequences gives F_{2}(2, N) ≥ \sqrt{2N} + o(N^{1/2}). In [C-R-T] it

is proved that F_{2}(g, N) ≥ \sqrt{\frac{g+[g/2]}{g+2[g/2]}}N^{1/2} + o(N^{1/2}).

Recently Lindstrom [L] generalized the argument of [K] to prove F_{h}(g, N) ≥ (gN)^{1/h} + o(N^{1/h}) for g = m^{h−1}, m ≥ 2.

In section 3 we obtain new lower bounds, improving the previous ones for h ≥ 3.

Theorem 1.2. Let h be an integer fixed. For any ϵ > 0, and for any g > g(ϵ, h)

F_{h}(g, N) ≥ ((1 − ϵ)\sqrt{\frac{π}{6}} \sqrt{h}gN)^{1/h} + o(N^{1/h}),

when N → ∞.

In our construction it is needed g to be big enough. This situation already appears in [L, (1.6)] and in fact our construction recover Lindstrom result.

2. Upper bounds

In this section we note that the use of Chebyshev inequality is wasteful in Alon’s argument. Instead of it we obtain a lower bound for the variance by observing that it cannot be smaller than the case where the integers are as compressed as possible.

Proof of Theorem 1.1.

Suppose that A ⊂ [1, N] is a B_{h}[g] sequence. Let the random variable Y be defined by Y = X_{1} + ⋯ + X_{h}, where the X_{j} are independent random variables uniformly distributed in A. We can obtain an upper bound in an easy way:

E ((Y − Ȳ)^{2}) = hE ((X − X̄)^{2}) ≤ hE ((X − (N + 1)/2)^{2}) ≤ h\frac{(N − 1)^{2}}{4} .

In order to estimate E ((Y − Ȳ)^{2}) we consider the multiset hA = {a_{1} + ⋯ + a_{h}; a_{i} ∈ A} = {s_{i} : i = 1, …, k}, where k = |A|^{h}.

|A|^{h}E ((Y − Ȳ)^{2}) = ∑_{s_{i}∈hA}(s_{i} − Ȳ)^{2}.

The minimum value of the variance of a set happens when the elements are as close as possible. We observe that the s_{i}’s take integer values which appear, at most, gh! times (because A is a B_{h}[g] sequence of integers). Then, the variance of hA is not less than the variance of the multiset

L = \{\overbrace{1, …, 1}^{h!g times}, 2, …, 2, …, l, …, l\}, where l = [k/gh!]. Hence,

|A|^{h}E ((Y − Ȳ)^{2}) ≥ ∑_{x∈L}(x − x̄)^{2} = ∑_{x∈L} x^{2} − |L|x̄^{2}

= gh! ∑_{k=1}^{l} k^{2} − gh!l (\frac{l + 1}{2})^{2} = gh!\frac{l(l + 1)(2l + 1)}{6} − gh!\frac{l(l + 1)^{2}}{4}

= gh!\frac{l(l + 1)(l + 2)}{12} ≥ \frac{k^{3}}{12(gh!)^{2}} − \frac{k}{12} ≥ |A|^{h} (\frac{|A|^{2h}}{12(gh!)^{2}} − \frac{1}{12}) .

Then we have proved

\frac{1}{12} (\frac{|A|^{2h}}{(gh!)^{2}} − 1) ≤ h\frac{(N − 1)^{2}}{4} ,

which implies

|A| ≤ ((gh!)^{2}(3h(N − 1)^{2} + 1))^{1/2h} ≤ (\sqrt{3h}h!gN)^{1/h}.

□

3. Lower bounds

Now we are interested in B_{h}[g] sequences as dense as possible. We will establish a generalization of Theorem 2.1 of [C-R-T] for any integer h.

The proof will go as Theorem 2.1 in [C-R-T]. So, first of all we will need the analogous definitions as 2.1 and 2.2 in [C-R-T] for this general context.

Definition 3.1. We say that A satisfies the B_{h}^{∗}[g] condition if the equation a_{1}+⋯+a_{h} = k has at most g solutions for any k, counting different those in distinct order.

Definition 3.2. We say that a sequence of integers C = {c_{i}} is a B_{h} (mod m) sequence if c_{i_{1}} + ⋯ + c_{i_{h}} = c_{j_{1}} + ⋯ + c_{j_{h}} (mod m) implies {c_{i_{1}}, …, c_{i_{h}}} = {c_{j_{1}}, …, c_{j_{h}}}.

Now we can establish the lemma generalizing Lemma 2.2 in [C-R-T].

Lemma 3.1. If A = {a_{i}} satisfies the B_{h}^{∗}[g] condition, and C is a B_{h} (mod m) sequence, then B = ∪_{i=0}^{k}(C + ma_{i}) is a B_{h}[g] sequence.

Proof. Suppose b_{1,1} + ⋯ + b_{h,1} = ⋯ = b_{1,g+1} + ⋯ + b_{h,g+1} for b_{i,j} ∈ B. We can write b_{i,j} = c_{i,j} + ma_{i,j} for some c_{i,j} ∈ C and a_{i,j} ∈ A. Let us order b_{i,j} such that, for any i and j, c_{i,j} ≤ c_{i+1,j}. Then, since c_{1,1} + ⋯ + c_{h,1} ≡ c_{1,j} + ⋯ + c_{h,j} (mod m) for any 1 ≤ j ≤ g + 1 we have that all the sets {c_{1,j}, …, c_{h,j}} are the same. Moreover the elements are ordered and so c_{i,j} = c_{i,1} for every i, j. This implies further that all the g + 1 sums a_{1,j} + ⋯ + a_{h,j} are equal hence, for some j, j′ we have a_{i,j} = a_{i,j′} for any 1 ≤ i ≤ h. Both together give us, for these j, j′, that b_{i,j} = b_{i,j′} for any 1 ≤ i ≤ h . □

In order to use Lemma 3.1, we have to find convenient sequences C and A on those conditions.

It is known [p. 81, H-R], that for m = p^{h} − 1, p prime, there exists a B_{h} (mod m) sequence C_{m} ⊂ [1, m] with cardinal |C_{m}| = p.

On the other hand we can choose the trivial A_{n} = {0, 1, …, n − 1} to get our bounds. Our next step is to find the greatest n so that A_{n} satisfies the B_{h}^{∗}[g] condition. Let us call n(g, h) to this n. We have

Proposition 3.1. F_{h}(g, N) ≥ n(g, h)^{1−1/h}N^{1/h} + o(N^{1/h}).

Proof. Let us take a prime p such that n(g, h)(p^{h} − 1) = N + o(N). Now we apply Lemma 3.1 with m = p^{h} − 1, A = A_{n(g,h)}. Then B ⊂ [1, n(g, h)m] and |B| = n(g, h)p. □

In order to estimate n(g, h) we define

r_{h}(n, k) = #{k = a_{1} + ⋯ + a_{h} : 0 ≤ a_{i} ≤ n − 1}

and M_{h}(n) = max_{k} r_{h}(n, k). Then n(g, h) is the greatest n such that M_{h}(n) ≤ g.

Proposition 3.2. M_{h}(n) ∼ n^{h−1} \frac{2}{π} ∫_{0}^{∞} (\frac{sin t}{t})^{h} dt

Proof. The obvious inequality M_{h}(2m − 1) ≤ M_{h}(2m) ≤ M_{h}(2m + 1) allows us to reduce the proof to n = 2m + 1, odd. In this case we can write r_{h}(n, k) = #{k − hm = a_{1} + ⋯ + a_{h} : −m ≤ a_{i} ≤ m}. It is now trivial to deduce

r_{h}(n, k) = \frac{1}{2π} ∫_{−π}^{π} ( ∑_{j=−m}^{m} e^{ijθ})^{h} e^{−i(k−hm)}dθ,

by expanding the h-power of the Dirichlet kernel. Hence, by a simple change of variables

r_{h}(n, k) = \frac{1}{2π} ∫_{−π}^{π} (\frac{sin((m + 1/2)θ)}{sin(θ/2)})^{h} e^{−i(k−hm)θ}dθ

= \frac{1}{π} (2m + 1)^{h−1} ∫_{−π(m+1/2)}^{π(m+1/2)} (\frac{sin t}{t})^{h} (\frac{t/(2m + 1)}{sin(t/(2m + 1))})^{h} e^{−i \frac{k−hm}{m+1/2} t}dt

= \frac{1}{π} (2m + 1)^{h−1} ∫_{−∞}^{∞} (\frac{sin t}{t})^{h} e^{−i \frac{k−hm}{m+1/2} t}dt + o(m^{h−1}).

Now observe that \frac{sin t}{t} is the fourier transform of the characteristic function of the interval [−1, 1]. Then ∫_{−∞}^{∞} (\frac{sin t}{t})^{h} e^{−ixt}dt is the value of the h-convolution of χ_{[−1,1]} at x, whi ch is maximum at x = 0 and so M_{h}(n) = max_{k} r_{h}(n, k) ∼ n^{h−1} \frac{2}{π} ∫_{0}^{∞} (\frac{sin t}{t})^{h} dt. □

Proposition 3.3. Let h be an integer fixed. For every ϵ > 0 and for every g > g(ϵ, h) we have

F_{h}(g, N) ≥ ((1 − ϵ)\frac{g}{m_{h}} N)^{1/h} + o(N^{1/h}).

where m_{h} = \frac{2}{π} ∫_{0}^{∞} (\frac{sin t}{t})^{h} dt.

Proof. It is consequence of Proposition 3.1 and 3.2 □

Proof of Theorem 1.2. We only need to study the behaviour of m_{h}. The upper bound m_{h} ≤ \sqrt{6/πh} for h ≥ 100 follows from the corresponding for J_{p} (1) in [3.3, L-N]. For 3 ≤ h ≤ 100 we get the bound by computing the explicit formula (17), (see (15)), of [N]

m_{h} = \frac{1}{(h − 1)!} ∑_{j<h/2}(h/2 − j)^{h−1}\binom{h}{j}(−1)^{j}.

In particular we get for the first few values

m_{3} = \frac{3}{4}, m_{4} = \frac{2}{3}, m_{5} = \frac{115}{192}, m_{6} = \frac{11}{20}, m_{7} = \frac{5587}{11520}

m_{8} = \frac{151}{315}, m_{9} = \frac{259723}{573550}, m_{10} = \frac{15619}{36288}.

The case h = 2 is covered in [C-R-T]. □

Remark 1. It is possible to find an explicit formula for r_{h}(n, k)

by using its generating function (∑_{k=0}^{n−1} x^{k})^{h} = ∑_{k} r_{h}(n, k)x^{k} together

with ∑ x^{n} = \frac{1}{1−x}. Moreover, one can prove that its maximum M_{h}(n) is attained at the mean, k_{h} = (n − 1)h/2 or k_{h} = ((n − 1)h + 1)/2. In this way one can obtain the explicit expression

M_{h}(n) = ∑_{j=0}^{h} \binom{\frac{n−1}{2}h + δ − nj + h − 1}{h − 1}\binom{h}{j}(−1)^{j},

where δ = 0 or 1/2 depending on the parity of (n − 1)h, which is useful for small values of h.

For example, for h = 3 we obtain M_{3}(n) = [\frac{3n^{2}+1}{4}], and Proposition 3.1 gives the more precise estimate

F_{3}(g, N) ≥ ([\sqrt{\frac{4g}{3}} ]^{2} N)^{1/3} + o(N^{1/3}).

Remark 2. Induction in r_{h}(n, k) = ∑_{j=0}^{n−1} r_{h−1}(n, k−j) immediately implies M_{h}(n) ≤ n^{h−1}. This and Proposition 3.1 recover Lindstrom result.

Acknowledgment.

We would like to express our gratitude to the referee for suggesting the analytical approach to prove Proposition 3.2. This has made the proof considerably shorter and more direct than our previous combinatorial method. We also would like to thank A. Córdoba and F. Chamizo for their comments in order to present the final proof of Proposition 3.2 as it appears now.

We are pleased to thank J.L. Nicolas for providing us with the very useful infornation in [L-N] and [N].

References

[B-Ch] R.C. Bose and S. Chowla, Theorems in the additive theory of numbers,

Comment. Math. Helv. 37 (1962/1963), 141–147.

[C-R-T] J. Cilleruelo, I. Ruzsa and C. Trujillo, Upper and lower bounds for B_{h}[g]

sequences, to appear in J. Number Theory.

[C1] J. Cilleruelo, New upper bounds for finite B_{h} sequences, preprint.

[C2] J. Cilleruelo, An upper bound for B_{2}[2] sequences, Journal of Combinatorial. Series A 89 (2000), 141-144.

[E-T] P. Erdős and P. Turan, On a problem of Sidon in additive number theory and on some related problems, J.London Math.Soc. 16 (1941), 212–215; Addendum (by P. Erdős), ibid 19 (1944), 208.

[H-R] H. Halberstam and K.F. Roth, Sequences, Springer-Verlag, New York, 1983.

[H] M. Helm, Upper bounds for B_{2}[g]-sets, preprint.

[K] M. Kolountzakis, Problems in the Additive Number Theory of General Sets, I. Sets with distinct sums., 1996, Available at http://www.math.uiuc.edu/ ∼ kolount/surveys.html.

[L-N] L. Lesieur and J.L. Nicolas, On the Eulerian numbers M_{n} = max_{1≤k≤n} A(n, k),

Europ. J. Comb. 13 (1992), 379–399.

[L] B. Lindstrom, B_{h}[g]-sequences from B_{h} sequences, Proc.Amer.Math.Soc. 128 (2000), 657-659.

[N] J.L. Nicolas, An Integral representation for Eulerian numbers, Coll. Math. Soc. János Bolyai 60, Sets, Graphs and Numbers Budapest, 1991.

[R] I. Ruzsa, Solving a linear equation I, Acta Arithmetica LXV.3 (1993). [S-S] A. Sarközy and V.T. Sos, The Mathematics of Paul Erdös, vol. I, Algorithms

and Combinatorics 13, Springer, 1996.

[S] J. Singer, A theorem in finite projective geometry and some applications to number theory, Trans.Am.math.Soc. 43 (1938), 377-385.

Departamento de Matematicas. Universidad Autónoma de Madrid. Madrid-28049.SPAIN

E-mail address: franciscojavier.cilleruelo@uam.es, jorge.jimenez@uam.es