Math Problems Vault

Problem 9.1.1

(1)(2)

The sum $A+B$ of subsets $A, B \subset \mathbb {R}$ or $A, B \subset \mathbb {Z}_m$ is the set $A+B := \left\{ a+b : a \in A, b \in B\right\}$ .

?

(1)

If $A, B \subset \mathbb {Z}_4$ , $\left|A+B\right| = \left|A\right| \neq 0$ and $\left|B\right| = 2$ , then $\left|A\right| \in \left\{ 2,4\right\}$ .

(2)

If $A, B \subset \mathbb {Z}_6$ , $\left|A+B\right| = \left|A\right| \neq 0$ and $\left|B\right| = 2$ , then $\left|A\right| \in \left\{ 3,6\right\}$ .

Problem 9.1.2

(1)(2)

The sum $A+B$ of subsets $A, B \subset \mathbb {R}$ is the set $A+B := \left\{ a+b : a \in A, b \in B\right\}$ . For any finite subsets $A, B \subset \mathbb {R}$

?

(1)

$\max \left\{ \left|A\right|, \left|B\right|\right\} \leqslant \left|A+B\right| \leqslant \left|A\right| \cdot \left|B\right|$ ;

(2)

$\left|A\right| \leqslant \left|A+A\right| \leqslant \dfrac {\left|A\right|(\left|A\right|+1)}{2}$ .

Problem 9.1.3

(1)(2)

?

(1)

If $A = \left\{ 2^j : j = 0, 1, \ldots , n-1\right\}$ , then $\left|A+A\right| = \dfrac {n(n+1)}{2}$ .

(2)

For any finite arithmetic progression $P \subset \mathbb {R}$ the inequality $\left|P+P\right| = 2\left|P\right|-1$ holds.

Remark.

?

Problem 9.1.3(1) gives an example of a subset for which the upper bound in Problem 9.1.2(2) is attained. Problem 9.1.3(2) gives an example of a subset for which the lower bound in Problem 9.1.2(2) is ``almost attained''. An example of a subset for which this bound is attained is an arbitrary one-element subset.

Problem 9.1.4

Kneser's theorem for $\mathbb {R}$ . For any finite subsets $A, B \subset \mathbb {R}$ the inequality $\left|A+B\right| \geqslant \left|A\right|+\left|B\right|-1$ holds.

The following $\mathbb {Z}_p$ -analogue may be used below without proof.

Cauchy--Davenport theorem. For any prime $p$ and any two subsets $A, B \subset \mathbb {Z}_p$ the following inequality holds:

\left|A+B\right| \geqslant \min \left\{ \left|A\right|+\left|B\right|-1, p\right\} .

?

Problem 9.1.5

(1)(2)

?

(1)

If $A, B \subset \mathbb {R}$ and $\left|A+B\right| = \left|A\right|$ , then $\left|B\right| = 1$ .

(2)

If $p$ is prime, $A, B \subset \mathbb {Z}_p$ and $\left|A+B\right| = \left|A\right|$ , then either $\left|B\right| \leqslant 1$ or $A = \mathbb {Z}_p$ .

Problem 9.1.6

Analogously to the sum of sets, one can define their difference: $A-B := \left\{ a-b : a \in A, b \in B\right\}$ .

Ruzsa's inequality. For any finite subsets $A, B, C \subset \mathbb {R}$

\left|C\right| \cdot \left|A-B\right| \leqslant \left|A-C\right| \cdot \left|B-C\right|.

?

Problem 9.1.7

(1)(2)(3)

?

(1)

For any nonempty finite subset $X \subset \mathbb {R}$ the inequality $\left|X-X\right| \leqslant \dfrac {\left|X+X\right|^2}{\left|X\right|}$ holds.

(2)

For any nonempty finite subsets $X, Y \subset \mathbb {R}$ the inequality $\left|X+X\right| \leqslant \dfrac {\left|X+Y\right|^2}{\left|Y\right|}$ holds.

(3)

For any finite subsets $X, Y \subset \mathbb {R}$ such that $X \cap Y \neq \emptyset$ , the inequality $\left|X+Y\right| \leqslant \dfrac {\left|X+X\right| \cdot \left|Y+Y\right|}{\left|X \cap Y\right|}$ holds.

Problem 9.1.8

For any nonempty subsets $A, B \subset \mathbb {R}$ the following statements are equivalent:

$\left|A+B\right| = \left|A\right| \cdot \left|B\right|$ ;
$\left|A-B\right| = \left|A\right| \cdot \left|B\right|$ ;
$\left|\left\{ (a_1,a_2,b_1,b_2) \in A \times A \times B \times B : a_1+b_1 = a_2+b_2\right\} \right| = \left|A\right| \cdot \left|B\right|$ ;
$\left|\left\{ (a_1,a_2,b_1,b_2) \in A \times A \times B \times B : a_1-b_1 = a_2-b_2\right\} \right| = \left|A\right| \cdot \left|B\right|$ ;
$\left|A \cap (\left\{ x\right\} -B)\right| = 1$ for any $x \in A+B$ ;
$\left|A \cap (B+\left\{ y\right\} )\right| = 1$ for any $y \in A-B$ ;
$(A-A) \cap (B-B) = \left\{ 0\right\}$ .

?

Problem 9.1.9

The sum of arbitrary subsets $X_1, X_2, \ldots , X_n \subset \mathbb {R}$ is defined as

X_1+X_2+\ldots +X_n := \left\{ x_1+x_2+\ldots +x_n : x_i \in X_i \text{ for any } 1 \leqslant i \leqslant n\right\} .

For an arbitrary subset $X \subset \mathbb {R}$ and any integer $k>0$ , set $kX := \underbrace{X+X+\ldots +X}_{k \text{ times}}$ .

Ruzsa's inequality (Problem 9.1.6) can be generalized to the case of a sum of $n$ sets.

Plünnecke--Ruzsa inequality. For any nonempty finite subsets $A_1, A_2, \ldots , A_n, B \subset \mathbb {R}$

\left|A_1+A_2+\ldots +A_n\right| \leqslant \frac{\left|A_1+B\right| \cdot \left|A_2+B\right| \cdot \ldots \cdot \left|A_n+B\right|}{\left|B\right|^{n-1}}.

For any finite subset $A \subset \mathbb {R}$ and arbitrary $n \in \mathbb {N}$ the inequalities $\left|A\right| \leqslant \left|nA\right| \leqslant \dbinom {\left|A\right|+n-1}{n}$ hold.

?

Problem 9.1.10

Analogously to the sum of sets, one can define their product: $AB := \left\{ ab : a \in A, b \in B\right\}$ .

If $A, B \subset \mathbb {Z}_5 \setminus \left\{ 0\right\}$ , $\left|AB\right| = \left|A\right| \neq 0$ and $\left|B\right|=2$ , then $\left|A\right| \in \left\{ 2,4\right\}$ .

?

Problem 9.1.11

(1)(2)

?

(1)

There exists $c>0$ such that for any finite set $A \subset \mathbb {R}$ the inequality $\max \left\{ \left|A+A\right|, \left|A \cdot A\right|\right\} \geqslant c\left|A\right|^{5/4}$ holds.

(2)

There exists $c>0$ such that for any arithmetic progression $P \subset \mathbb {R}$ of length greater than 3 the inequality $\left|P \cdot P\right| > c\left|P\right|^{5/4}$ holds.

Remark.

?

In fact, if $P$ is an arithmetic progression of length $n$ in the set of integers, then the bound from Problem 9.1.11(2) can be improved. Namely, for any $\varepsilon \in (0,2)$ there exists $c>0$ such that $\left|P \cdot P\right| \geqslant c\left|P\right|^{\varepsilon }$ . The proof of this fact uses nontrivial theorems of number theory and therefore lies beyond the scope of this book.

Problem 9.1.12

Let $P$ be a set of points in the plane, and $L$ a set of lines in the plane. The number of incidences $I(P,L) := \left|\left\{ (p,l) \in P \times L : p \in l\right\} \right|$ is the number of pairs of the form (point on the line, line), where the line and the point are taken from the corresponding sets.

An arbitrary finite nonempty subset $A \subseteq \mathbb {R}$ is given. Denote by $\mathscr {L}$ the family of lines in the plane given by the equation $y=a(x-b)$ , where $a,b \in A$ . Let $\mathscr {P} := (A+A) \times (A \cdot A)$ . Prove that the total number of incidences between the lines of $\mathscr {L}$ and the points of $\mathscr {P}$ is at least $\left|A\right|^3$ .

?