Past exam of the mathematics course of the University of Cambridge / 2021 / iii / Paper 129 / 1 / d

Table of contents
- Solution d

Solution

Let

e_{1}, \dots, e_{m}

be the standard basis of

F_{2}^{m}

and take

A_{m} = {0, e_{1}, \dots, e_{m}} .

Its sumset consists of zero, the

m

basis vectors, and the

(2 m)

sums of two distinct basis vectors. Thus

K_{m} = \frac{∣ A _{m} + A _{m} ∣}{∣ A _{m} ∣} = \frac{1 + m + ( 2 m )}{m + 1} = \frac{m}{2} + \frac{1}{m + 1} .

x + H

contains

A_{m}

, then every difference of two elements of

A_{m}

lies in

H

. In particular every

e_{i}

lies in

H

, so

H = F_{2}^{m}

and

\frac{∣ H ∣}{∣ A _{m} ∣} = \frac{2 ^{m}}{m + 1} .

Since

m = 2 K_{m} + O (1)

, this ratio is eventually much larger than

K_{m}^{- 1} 2^{K_{m}}

. Hence no bound valid for all

K

can replace the factor in part c by a function smaller than

K^{- 1} 2^{K}

.

 Ancestors (10)

 View article source

 Discussion (0)

There are no discussions about this article yet.

 Articles by others on the same topic (0)

There are currently no matching articles.

  See all articles in the same topic Create my own version