TY - JOUR

T1 - Finding large co-Sidon subsets in sets with a given additive energy

AU - Silva, Manuel Almeida

PY - 2013/1/1

Y1 - 2013/1/1

N2 - For two finite sets of integers A and B their additive energy E(A, B) is the number of solutions to a + b = a' + b', where a, a' is an element of A and b, b' is an element of B. Given finite sets A, B subset of Z with additive energy E (A, B) = vertical bar A vertical bar vertical bar B vertical bar + E, we investigate the sizes of largest subsets A' subset of A and B' subset of B with all vertical bar A'vertical bar vertical bar B'vertical bar sums a + b, a is an element of A', b is an element of B', being different (we call such subsets A', B' co-Sidon). In particular, for vertical bar A vertical bar = vertical bar BI vertical bar = n we show that in the case of small energy, n <= E = E(A, B) vertical bar A vertical bar vertical bar B vertical bar << n(2), one can always find two co-Sidon subsets A', B' with sizes vertical bar A'vertical bar = k, vertical bar B'vertical bar = l, whenever k, l satisfy kl(2) << n(4)/E. An example showing that this is best possible up to the logarithmic factor is presented. When the energy is large, E >> n(3), we show that there exist co-Sidon subsets A', B' of A, B with sizes vertical bar A vertical bar = k, vertical bar B'vertical bar = l whenever k, l satisfy k << n and show that this is best possible. These results are extended (nonoptimally, however) to the full range of values of E.

AB - For two finite sets of integers A and B their additive energy E(A, B) is the number of solutions to a + b = a' + b', where a, a' is an element of A and b, b' is an element of B. Given finite sets A, B subset of Z with additive energy E (A, B) = vertical bar A vertical bar vertical bar B vertical bar + E, we investigate the sizes of largest subsets A' subset of A and B' subset of B with all vertical bar A'vertical bar vertical bar B'vertical bar sums a + b, a is an element of A', b is an element of B', being different (we call such subsets A', B' co-Sidon). In particular, for vertical bar A vertical bar = vertical bar BI vertical bar = n we show that in the case of small energy, n <= E = E(A, B) vertical bar A vertical bar vertical bar B vertical bar << n(2), one can always find two co-Sidon subsets A', B' with sizes vertical bar A'vertical bar = k, vertical bar B'vertical bar = l, whenever k, l satisfy kl(2) << n(4)/E. An example showing that this is best possible up to the logarithmic factor is presented. When the energy is large, E >> n(3), we show that there exist co-Sidon subsets A', B' of A, B with sizes vertical bar A vertical bar = k, vertical bar B'vertical bar = l whenever k, l satisfy k << n and show that this is best possible. These results are extended (nonoptimally, however) to the full range of values of E.

KW - additive energy

KW - co-Sidon sets

KW - graph

KW - Sidon set

U2 - 10.1016/j.ejc.2013.04.002

DO - 10.1016/j.ejc.2013.04.002

M3 - Article

VL - 34

SP - 1144

EP - 1157

JO - European Journal Of Combinatorics

JF - European Journal Of Combinatorics

SN - 0195-6698

IS - 7

ER -