An example concerning set addition in F₂^n

Abstract: We construct sets

A, B

in a vector space over

m a t h b b F_{2}

with the property that

A

is "statistically" almost closed under addition by

B

in the sense that

a + b

almost always lies in

A

when

a i n A, b i n B

, but which is extremely far from being "combinatorially" almost closed under addition by

B

: if

A^{'} s u b s e t A

,

B^{'} s u b s e t B

and

A^{'} + B^{'}

is comparable in size to

A^{'}

then

| B^{'} | l e s s a p p r o x | B |^{1 / 2}

.

Review text

The set \(L_{d}\) of vectors in \(\mathbb{F}_{2}^{D}\) with Hamming weight \(d\) is called a layer. The union \(L_{s} \cup \dots{} \cup L_{s+k-1}\) of \(k\) consecutive layers is called a band of width \(k\) in \(\mathbb{F}_{2}^{D}\). In this paper the authors construct arbitrary large finite sets \(A\) and \(B\) in some vector space over \(\mathbb{F}_{2}\) with the property that \(\mathbb{P}(a+b\in A|a\in A,b\in B) \ge 1 - \delta\) such that if \(A^{'} \subset A\) and \(B^{'} \subset B\) satisfy \(|A^{'} + B^{'}| \le K|A^{'}|\), then \(|B^{'}| = O_{K,\delta}(|B|^{1/2})\), where \(0 < \delta < 1 < K\). The set \(A\) contains a direct product of \(m\) bands in copies of \(\mathbb{F}_{2}^{m}\). The set \(B\) is formed by the standard basis vectors in \((\mathbb{F}_{2}^{m})^{m}\).

Recommendations

Cites work

Cited in

(3)

This page was built for publication: An example concerning set addition in \(\mathbb{F}_2^n\)

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