A single set improvement to the 3k - 4 theorem

Additive bases, including sumsets (11B13) Other combinatorial number theory (11B75) Inverse problems of additive number theory, including sumsets (11P70)

Abstract: The

3 k - 4

Theorem is a classical result which asserts that if

A,, B s u b s e t e q m a t h b b Z

are finite, nonempty subsets with �egin{equation}label{hyp}|A+B|=|A|+|B|+rleq |A|+|B|+min{|A|,,|B|}-3-delta,end{equation} where

d e l t a = 1

if

A

and

B

are translates of each other, and otherwise

d e l t a = 0

, then there are arithmetic progressions

P_{A}

and

P_{B}

of common difference such that

A s u b s e t e q P_{A}

,

B s u b s e t e q P_{B}

,

| B | l e q | P_{B} | + r + 1

and

| P_{A} | l e q | A | + r + 1

. It is one of the few cases in Freiman's Theorem for which exact bounds on the sizes of the progressions are known. The hypothesis above is best possible in the sense that there are examples of sumsets

A + B

having cardinality just one more, yet

A

and

B

cannot both be contained in short length arithmetic progressions. In this paper, we show that the hypothesis above can be significantly weakened and still yield the same conclusion for one of the sets

A

and

B

. Specifically, if

| B | g e q 3

,

s g e q 1

is the unique integer with

(s-1)sleft(frac{|B|}{2}-1 ight)+s-1<|A|leq s(s+1)left(frac{|B|}{2}-1 ight)+s,

and �egin{equation}label{hyp2} |A+B|=|A|+|B|+r< (frac{|A|}{s}+frac{|B|}{2}-1)(s+1),end{equation} then we show there is an arithmetic progression

P_{B} s u b s e t e q m a t h b b Z

with

B s u b s e t e q P_{B}

and

| P_{B} | l e q | B | + r + 1

. The above hypothesis is best possible (without additional assumptions on

A

) for obtaining such a conclusion.

Review text

It is well known that, for any finite set \(A\) of integers with \(|A+A|\le 3|A|-4\), Freiman's theorem implies that \(A\) is contained in an arithmetic progression of length \(\le|A+A|- |A|+1\). Apart from an additional conclusion concerning a long arithmetic progression in the sumset, the extended \(3k-4\) theorem asserts that, for finite, nonempty sets \(A\) and \(B\) of integers with \(|A+B|\le |A|+|B|+ \min\{|A|, |B|\}-3-\delta\), where \(\delta=1\) if \(A\) and \(B\) are translates of each other and \(\delta=0\) otherwise, there are arithmetic progressions \(P_A\) and \(P_B\) of integers with common difference such that \(A\subseteq P_A\), \(B\subseteq P_B\), \(|P_A|\le |A+B|-|B|+1\) and \(|P_B|\le |A+B|-|A|+1\). In the paper under review the author shows that the hypothesis on \(|A+B|\) can be significantly weakened and still yield the same conclusion for one of the finite sets \(A\) and \(B\) of integers. Specifically, if \(|A|\ge 1\), \(|B|\ge 3\) and \(|A+B|< \left(\frac{|A|}{s}+ \frac{|B|}{2}- 1\right)(s+1)\), where \(s\ge 1\) is the unique integer with \[(s-1)s\Biggl(\frac{|B|}{2}-1\Biggr)+ s-1<|A|\le s(s+1)\Biggl(\frac{|B|}{2}-1\Biggr)+s,\] then there is an arithmetic progression \(P_B\) and \(B\subseteq P_B\) and \(|P_B|\le |A+B|- |A|+1\).

Recommendations

Cites work

Cited in

(9)

This page was built for publication: A single set improvement to the \(3k - 4\) theorem

Report a bug (only for logged in users!)Click here to report a bug for this page (MaRDI item Q2187135)