ENS Mathématiques 1 MP 2009Sujet et corrigé

Pas encore noté

Algèbre générale

Explorer les annales

BanqueX-ENS Année2009 FilièreMP MatièreMathématiques

Annales X-ENS MP Mathématiques X-ENS MP 2009 MP Mathématiques Mathématiques 2009

Téléchargements

Télécharger le sujet (PDF)

Corrigé

Lire en ligne LaTeX Word

Rapport du jury : non disponible

Présentation du sujet

Combinatoire additive : sommes de parties, progressions arithmétiques et théorème de Freiman-Ruzsa-Chang

Le problème étudie les propriétés combinatoires des sommes de parties d'un groupe abélien, en lien avec la structure des progressions arithmétiques, pour aboutir à la démonstration du théorème de Freiman-Ruzsa-Chang. Il combine des outils de nature arithmétique (formes quadratiques définies positives sur les réseaux) et analytique (transformation de Fourier sur Z/NZ), combinés dans une avant-dernière partie pour montrer qu'un ensemble 2A-2A contient une progression arithmétique de dimension et taille contrôlées, avant la démonstration finale du théorème.

1Partie I : sommes de partiesÉtablir des inégalités générales sur les cardinaux des sommes de parties d'un groupe abélien et caractériser les cas d'égalité, notamment en lien avec les progressions arithmétiques.
2Partie II : valeurs aux entiers de formes quadratiques définies positivesÉtudier les bases entières de Z^n et démontrer, pour une forme quadratique définie positive, un encadrement du minimum de ses valeurs entières en fonction de son discriminant.
3Partie III : transformation de Fourier et sommes d'ensemblesUtiliser la transformation de Fourier sur Z/NZ pour relier le cardinal des sommes de parties aux coefficients de Fourier de leur fonction indicatrice.
4Partie IV : progressions arithmétiquesCombiner les résultats arithmétiques et analytiques des parties précédentes pour montrer qu'un ensemble de la forme 2A-2A contient une progression arithmétique de dimension et de taille contrôlées.
5Partie V : théorème de Freiman-Ruzsa-ChangDémontrer le théorème de Freiman-Ruzsa-Chang, qui borne la dimension et la taille d'une progression arithmétique contenant une partie donnée de Z en fonction du rapport des cardinaux de A+A et de A.

Ces sujets peuvent vous intéresser

Lecture du sujet en ligne

L'énoncé complet, avec les formules et les figures, sans ouvrir le PDF.

Sujet en PDF

Filière MP

MATHÉMATIQUES MPI 1

Épreuve commune aux ENS de Paris, Lyon et Cachan

Durée : 6 heures

L'usage de calculatrice est interdit

Préambule

Le problème est consacré à quelques propriétés de nature combinatoire des groupes abéliens.

Soit

G

un groupe abélien et soit

A

une partie non vide de

G

; on relie ainsi des propriétés atypiques des cardinaux des ensembles

A, A + A

, d'une part, notamment le fait que le cardinal de

A + A

soit «petit» par rapport à celui de

A

et des propriétés algébriques de l'ensemble

A

, comme le fait d'être une progression arithmétique.

Le résultat principal du problème, le théorème de Freiman-Rusza-Chang, affirme que toute partie non vide

A

Z

est contenue dans une progression arithmétique de dimension et taille contrôlées en fonction du rapport

σ = Card(A + A)/Card(A)

. Il est démontré à la fin de la partie V .

La partie I développe quelques généralités sur les sommes d'ensembles. La démonstration du théorème de Freiman-Rusza-Chang utilise des arguments de nature arithmétique (valeurs aux vecteurs à coordonnées entières de formes quadratiques définies positives) qui font l'objet de la partie II et d'autres de nature analytique (séries de Fourier) qui sont développés dans la partie III.

Ces trois premières parties sont indépendantes l'une de l'autre.
Leurs arguments sont combinés dans la partie IV pour démontrer que l'ensemble

2A - 2A

contient une progression arithmétique de dimension et taille contrôlée en fonction de

σ

. Le théorème de Freiman-Rusza-Chang fait alors l'objet de la partie V et clôt le problème.

Notations

Les lettres

N, N^*, Z, R

C

désignent respectivement l'ensemble des entiers naturels, celui des entiers naturels strictement positifs, l'anneau des entiers relatifs, le corps des nombres réels et le corps des nombres complexes. On note

ℜ(z), ℑ(z)

|z|

la partie réelle, la partie imaginaire et le module d'un nombre complexe

z

La fonction log est la fonction logarithme népérien, réciproque de la fonction exponentielle. On désigne par cosh et sinh les fonctions «cosinus hyperbolique» et «sinus hyperbolique»; elles sont définies pour tout nombre complexe

z

par les relations

cosh(z) = 1/2(e^z + e^(- z)) et sinh(z) = 1/2(e^z - e^(- z))

Une partition d'un ensemble

A

est un ensemble de parties de

A

deux à deux disjointes dont la réunion est égale à

A

. Si

A

est un ensemble fini, on notera

Card(A)

son cardinal.

n

est un entier naturel,

n!

désigne le produit

1 \cdot 2\dotsn

de tous les entiers de 1 à

n

; par convention, on pose

0! = 1

. Si

n

p

sont des entiers naturels, on note

(n/p)

l'entier

n!/p!(n - p)!

(coefficient binomial).

L'espace vectoriel

R^n

sera muni de la norme euclidienne standard telle que

‖x⃗‖^2 = x_1^2 + \dots + x_n^2

x⃗ = (x_1, \dots, x_n)

. La base canonique de cet espace est la famille

(e⃗_1, \dots, e⃗_n)

telle que

x⃗ = x_1 e⃗_1 + \dots + x_n e⃗_n

x⃗ = (x_1, \dots, x_n)

Soit

N

un entier naturel strictement positif; si

a

b

sont des entiers relatifs, on note

a \equiv b(modN)

pour dire que

a

b

sont congrus modulo

N

, c'est-à-dire que

a - b

est multiple de

N

. La classe de congruence modulo

N

d'un entier relatif

x

est l'ensemble des entiers relatifs qui sont congrus à

x

modulo

N

. On note

Z/NZ

l'anneau des entiers modulo

N

Soit

G

un groupe abélien dont la loi de groupe est notée additivement. Si

A, B

sont des parties de

G

, on note respectivement

A + B

A - B

l'ensemble des sommes

a + b

et l'ensemble des différences

a - b

, où

a

parcourt

A

b

parcourt

B

. Lorsque ces parties ne sont pas vides, on pose aussi

d_R(A, B) = log(Card(A - B))/(\sqrt(Card(A)Card(B))).

A

est une partie de

G

n

est un entier naturel, on note

nA

l'ensemble

A + A + \dots + A

(où il y a

n

termes). Enfin, si

b \in G

, on fera l'abus de notation consistant à noter

b + A

l'ensemble

{b} + A

Soit

d

un entier naturel tel que

d > 0

; soit

T

un entier naturel. On dit qu'une partie

P

G

est une progression arithmétique de dimension

d

et de taille

T

s'il existe des éléments

x_0, \dots, x_d

G

et des entiers naturels non nuls

N_1, \dots, N_d

tels que

T = N_1\dotsN_d

P = {x_0 + ∑_(j = 1)^d n_j x_j; 0 ⩽ n_j ⩽ N_j − 1}

; on dit qu'une telle progression arithmétique est propre si l'on a

Card(P) = T

I. Sommes de parties

Soit $t$ un entier naturel non nul et soit $N$ un entier naturel.
a) Soit $n$ et $p$ des entiers naturels tels que $n ⩾ p$ ; démontrer l'égalité

(p/p) + ((p + 1)/p) + \dots + (n/p) = ((n + 1)/(p + 1)).

b) Démontrer que l'ensemble des

t

-uplets (

a_1, \dots, a_t

) d'entiers naturels tels que

a_1 + \dots + a_t = N

a pour cardinal

((N + t - 1)/N)

.
c) Vérifier l'encadrement

1/(N!)t^N ⩽ ((N + t - 1)/N) ⩽ t^N.

Soit $G$ un groupe abélien fini et soit $A, B$ des parties non vides de $G$ telles que $Card(A) + Card(B) > Card(G)$ .
a) Démontrer que $G = A + B$ .
b) Donner un exemple où l'on a $Card(A) + Card(B) = Card(G)$ mais $G \neq A + B$ .
Soit $G$ un groupe abélien.
a) Si $A$ et $B$ sont des parties finies et non vides de $G$ , démontrer les inégalités

max(Card(A), Card(B)) ⩽ Card(A + B) ⩽ Card(A)Card(B).

b) Soit

A

une partie finie et non vide de

G

. Démontrer pour tout entier naturel

n ⩾

1 les inégalités

Card(A) ⩽ Card(2A) ⩽ \dots ⩽ Card(nA) ⩽ ((Card(A) + n - 1)/n).

Soit $A$ et $B$ des parties finies et non vides de $Z$ .
a) Démontrer que $Card(A + B) ⩾ Card(A) + Card(B) - 1$ .
b) On suppose que $Card(A + B) = Card(A) + Card(B) - 1$ et que $A$ et $B$ ne sont pas des singletons. Démontrer qu'il existe des entiers $a, b$ et $d$ tels que

A = {a, a + d, \dots, a + (Card(A) - 1)d} et B = {b, b + d, \dots, b + (Card(B) - 1)d}.

Soit $G$ un groupe abélien et soit $A, B$ des parties finies et non vides de $G$ .
a) Soit $H$ l'ensemble des éléments $g$ de $G$ tels que $A = g + A$ . Démontrer que $H$ est un sous-groupe fini de $G$ .
b) Démontrer que $Card(A + B) = Card(A)$ si et seulement s'il existe $b \in G$ tel que $B \subset b + H$ .
Soit $G$ un groupe abélien et soit $A, B, C$ des parties finies et non vides de $G$ . Démontrer que $d_R(A, B) ⩾ 0$ . Démontrer aussi l'«inégalité triangulaire»:

d_R(A, C) ⩽ d_R(A, B) + d_R(B, C).

Soit $A$ et $B$ des parties finies non vides de $G$ . Démontrer que $d_R(A, B) = 0$ si et seulement s'il existe un sous-groupe fini $H$ de $G$ et des éléments $a, b \in G$ tels que $A = a + H$ et $B = b + H$ .

II. Valeurs aux entiers de formes quadratiques définies positives

On dira qu'une famille (

v⃗_1, \dots, v⃗_n

) de l'espace vectoriel

R^n

est une base entière si elle est formée d'éléments de

Z^n

et si tout élément de

Z^n

est combinaison linéaire à coefficients entiers des

v⃗_i

Soit $(v⃗_1, \dots, v⃗_n)$ une famille d'éléments de $Z^n$ . Démontrer que c'est une base entière si et seulement si son déterminant (dans la base canonique) est égal à $\pm 1$ .
Pour $v⃗ = (a_1, \dots, a_n) \in Z^n$ , on pose $s(v⃗) = |a_1| + \dots + |a_n|$ .

Soit

v⃗ \in Z^n

un vecteur non nul dont les coordonnées sont premières entre elles dans leur ensemble. Montrer par récurrence sur

s(v⃗)

qu'il existe une base entière

(v⃗_1, \dots, v⃗_n)

R^n

telle que

v⃗ = v⃗_1

. (Si

v⃗ = (a_1, \dots, a_n)

, choisir

i \in {1, \dots, n}

de sorte que

|a_i|

soit minimal et considérer des vecteurs

w⃗ = (b_1, \dots, b_n)

tels que

b_i = a_i

b_j

est de la forme

a_j - qa_i

pour

j \neq i

.)
3. Soit

Φ

une forme quadratique

surR^n

. On note disc

(Φ)

le déterminant de la matrice de

Φ

dans la base canonique de

R^n

Soit

u

un endomorphisme de

R^n

Φ_1

la forme quadratique

Φ \circ u

. Démontrer que

disc(Φ_1) = det(u)^2 disc(Φ)

.
4. Soit

Φ

une forme quadratique définie positive sur

R^n

. On pose

m(Φ) = inf_(v⃗ ∈ Z^n∖{0})Φ(v⃗)

a) Démontrer que

m(Φ) > 0

et qu'il existe un vecteur

v⃗_1 ∈ Z^n∖{0}

tel que

Φ(v⃗_1) = m(Φ)

.
b) Démontrer qu'il existe une base entière de

R^n

de la forme (

v⃗_1, \dots, v⃗_n

), où

Φ(v⃗_1) = m(Φ)

.
c) Montrer qu'il existe une forme linéaire

L_1

sur

R^n

et une forme quadratique

Φ_1

sur

R^(n - 1)

telles que

L_1(1, 0, \dots, 0) = 1;; Φ(x_1 v⃗_1 + \dots + x_n v⃗_n) = m(Φ)L_1(x_1, \dots, x_n)^2 + Φ_1(x_2, \dots, x_n)

pour tout

(x_1, \dots, x_n) \in R^n

.
d) Démontrer que

Φ_1

est une forme quadratique définie positive sur

R^(n - 1)

, et que l'on a l'égalité disc

(Φ) = m(Φ)disc(Φ_1)

.
e) Démontrer que pour tout

(x_2, \dots, x_n) \in Z^(n - 1)

, il existe

x_1 \in Z

tel que

|L_1(x_1, \dots, x_n)| ⩽ 1/2

.
f) Démontrer que

m(Φ) ⩽ 4/3m(Φ_1)

.
g) En déduire par récurrence que

m(Φ) ⩽ (4/3)^((n - 1)/2)disc(Φ)^(1/n)

.
h) Démontrer par récurrence qu'il existe une base entière (

v⃗_1, \dots, v⃗_n

) de

R^n

telle que

Φ(v⃗_1)\dotsΦ(v⃗_n) ⩽ (4/3)^(n(n - 1)/2)disc(Φ).

III. Transformation de Fourier et sommes d'ensembles

Soit

N

un entier tel que

N ⩾ 1

; posons

ω = exp(2iπ/N)

. Si

a

est un élément de

Z/NZ

, on notera

ω^a

le nombre complexe

ω^n

, où

n

est un élément quelconque de la classe de congruence

a

Pour toute application

f : Z/NZ \to C

, on définit alors une application

f^ : Z/NZ \to C

en posant

f^(x) = \sum_(a \in Z/NZ)f(a)ω^(ax), pour tout x \in Z/NZ

f

g

sont des applications de

Z/NZ

dans

C

, on définit aussi une application

f*g

Z/NZ

dans

C

par la formule

(f*g)(a) = \sum_(t \in Z/NZ)f(t)g(a - t), pour tout a \in Z/NZ.

Pour

a \in Z/NZ

, on note

d_N(a)

le minimum des

|x/N|

où

x

parcourt l'ensemble des éléments de la classe de congruence

a

. Si

X

est une partie de

Z/NZ

r

un nombre réel strictement positif, on définit

ℬ(X, r)

comme l'ensemble des

a \in Z/NZ

tels que

d_N(ax) ⩽ r

pour tout

x \in X

Soit $a \in Z/NZ$ . Démontrer que $\sum_(x \in Z/NZ)ω^(ax)$ vaut $N$ si $a = 0$ , et vaut 0 sinon.
Soit $f, g$ des applications de $Z/NZ$ dans $C$ . Démontrer les formules suivantes :
a) pour $a \in Z/NZ, f(a) = 1/N\sum_(x \in Z/NZ)f^(x)ω^(- ax)$ ;
$b)$ on a $\sum_(a \in Z/NZ)f(a)g(a) = 1/N\sum_(x \in Z/NZ)f^(x)g^(- x)$ ;
c) pour tout $x \in Z/NZ$ , on a $(f*g)^-(x) = f^(x)g^(x)$ .
Soit $A$ une partie de $Z/NZ$ et soit $f_A : Z/NZ \to C$ sa fonction indicatrice.
a) Démontrer les formules

1/N∑_(x ∈ Z/NZ)|f_A ˆ(x)|^2 = Card(A);; 1/N∑_(x ∈ Z/NZ)|f_A ˆ(x)|^4 = Card({(a_1, a_2, a_3, a_4) ∈ A^4; a_1 + a_2 = a_3 + a_4}).

b) Démontrer qu'un élément

a

Z/NZ

appartient à

2A - 2A

si et seulement si l'expression

\sum_(x \in Z/NZ)|f_A ˆ(x)|^4 ω^(- ax)

n'est pas nulle.
4. Soit

κ

un entier naturel. On dit qu'une suite (

x_1, \dots, x_κ

) d'éléments de

Z/NZ

est indépendante si la seule suite

(ε_1, \dots, ε_k)

d'entiers de

{ - 1, 0, 1}

telle que

\sum_(j = 1)^κ ε_j x_j = 0

est la suite

(0, \dots, 0)

Soit

X

une partie de

Z/NZ

et soit

(x_1, \dots, x_κ)

une suite indépendante d'éléments de

X

telle que

κ

soit maximal.
a) Démontrer que

X

est contenu dans l'ensemble des éléments de

Z/NZ

de la forme

\sum_(j = 1)^k ε_j x_j

, où

ε_j ∈ { − 1, 0, 1}

pour tout

j

.
b) On pose

K = {x_1, …, x_κ}

. Démontrer que pour tout nombre réel

r > 0

, l'ensemble

ℬ(X, r)

contient l'ensemble

ℬ(K, r/κ)

. (Ces ensembles sont définis au début de cette partie.)

Les trois questions suivantes ont pour but de majorer la taille maximale d'une suite indépendante formée d'éléments d'une partie X. Cet objectif est atteint à la question III.7, c).
5. a) Soit

t

un nombre réel ; démontrer que la fonction

F

R

dans

R

donnée par

F(x) = exp(tx)

est convexe.
b) Soit

t

y

des nombres réels tels que

|y| ⩽ 1

; démontrer que

exp(ty) ⩽ cosh(t) + ysinh(t)

.
c) Pour

t \in R

, démontrer que

cosh(t) ⩽ exp(t^2/2)

.
6. Soit

(x_1, \dots, x_κ)

une suite indépendante d'éléments de

Z/NZ

, soit (

c_1, \dots, c_κ

) une suite de nombres complexes et soit

g : Z/NZ \to C

l'application définie par

g(a) = \sum_(j = 1)^κ ℜ(c_j ω^(- ax_j)), pour a \in Z/NZ

a) Calculer

g^(x)

pour

x \in Z/NZ

. En déduire que

\sum_(a \in Z/NZ)g(a) = 0

.
b) Démontrer que

\sum_(a \in Z/NZ)g(a)^2 = 1/2N\sum_(j = 1)^K|c_j|^2

.
c) Pour

j \in {1, \dots, κ}

, soit

x~_j

un entier naturel dans la classe de congruence

x_j

et soit

θ_j

un nombre réel. Démontrer que pour toute partie non vide

J

{1, \dots, κ}

\sum_(a = 0)^(N - 1)\prod_(j \in J)cos((2π)/Nax~_j + θ_j) = 0

d) Démontrer que pour tout

t \in R

, on a

1/N\sum_(a \in Z/NZ)exp(tg(a)) ⩽ exp(1/Nt^2\sum_(a \in Z/NZ)g(a)^2)

Dans cette question et dans la suivante, on considère la situation suivante. Soit $ρ$ et $α$ des nombres réels tels que $0 < ρ < 1$ et $0 < α < 1$ . Soit $A$ une partie de $Z/NZ$ telle que $Card(A) ⩾ αN$ et soit $f_A$ sa fonction indicatrice. Soit $X$ l'ensemble des $x \in Z/NZ$ tels que $|f_A ˆ(x)| ⩾ ρCard(A)$ .
a) Soit $κ$ un entier naturel et soit ( $x_1, \dots, x_κ$ ) une suite indépendante de $Z/NZ$ telle que $x_j \in X$ pour tout $j \in {1, \dots, κ}$ . Pour $a \in Z/NZ$ , on pose

g(a) = \sum_(j = 1)^k ℜ(f_A ˆ(x_j)ω^(- ax_j)).

Démontrer que

\sum_(a \in Z/NZ)f_A(a)g(a) = 2/N\sum_(a \in Z/NZ)g(a)^2.

b) Minorer l'expression

\sum_(a \in A)exp(tg(a))

, pour

t \in R

, et démontrer que

\sum_(a \in Z/NZ)g(a)^2 ⩽ NCard(A)^2 log(1/α).

c) En déduire que

κ ⩽ 2ρ^(- 2)log(1/α)

.
8. On pose

σ = Card(A + A)/Card(A)

et on choisit

ρ = 1/2\sqrtσ

.
a) Démontrer que

\sum_(x \in Z/NZ)|f_A ˆ(x)|^4 ⩾ α^3 N^4/σ

.
b) Démontrer que

\sum_(x \notin X)|f_A ˆ(x)|^4 ⩽ α^3 N^4/4σ

.
c) Démontrer que

2A - 2A

contient

ℬ(X, 1/16)

. (On pourra utiliser, après l'avoir démontrée, l'inégalité

|1 - ω^a| ⩽ 2πd_N(a)

pour tout

a \in Z

.)
d) On pose

r = (128σlog(1/α))^(- 1)

. Démontrer qu'il existe une partie

K

Z/NZ

de cardinal

⩽ 8σlog(1/α)

telle que

2A - 2A

contienne

ℬ(K, r)

IV. Progressions arithmétiques

Soit $N$ un nombre premier, soit $n$ un entier naturel non nul. On désigne par $N \cdot Z^n$ l'ensemble des éléments de $Z^n$ dont toutes les coordonnées sont divisibles par $N$ . Soit $ξ⃗ = (ξ_1, \dots, ξ_n)$ un élément de $Z^n$ qui n'appartient pas à $N \cdot Z^n$ .
a) Démontrer qu'il existe des entiers relatifs $a, b_1, \dots, b_n$ tels que les nombres entiers $aξ_1 + Nb_1, aξ_2 + Nb_2, \dots, aξ_n + Nb_n$ soient premiers entre eux dans leur ensemble.
b) Soit $L$ l'ensemble des éléments $x⃗$ de $Z^n$ tels qu'il existe $u \in Z$ de sorte que $x⃗ - uξ⃗ \in N \cdot Z^n$ . Démontrer qu'il existe une base entière ( $v⃗_1, \dots, v⃗_n$ ) de $R^n$ telle que $L$ soit l'ensemble des combinaisons linéaires $t_1 v⃗_1 + Nt_2 v⃗_2 + \dots + Nt_n v⃗_n$ , pour $(t_1, \dots, t_n) \in Z^n$ . (On pourra commencer par trouver un vecteur $v⃗_1 \in L$ dont les coordonnées sont premières entre elles.)
c) Démontrer qu'il existe une base ( $w⃗_1, \dots, w⃗_n$ ) de $R^n$ formée de vecteurs appartenant à $L$ tels que $‖w⃗_1‖\dots‖w⃗_n‖ ⩽ (4/3)^(n(n - 1)/4)N^(n - 1)$ . (On pourra introduire la forme quadratique sur $R^n$ définie par $Φ(x_1, \dots, x_n) = ‖x_1 v⃗_1 + Nx_2 v⃗_2 + \dots + Nx_n v⃗_n‖^2$ et utiliser les résultats de la partie II.)
On conserve les notations de la question précédente.

Pour tout

i \in {1, \dots, n}

, soit

x_i

un entier relatif tel que

w⃗_i - x_i ξ⃗

appartienne à

N \cdot Z^n

. On note

X

la partie de

Z/NZ

formée des classes des

ξ_i

modulo

N

. Soit

r

un nombre réel
strictement positif tel que

r < 1/2

. Soit

M

l'ensemble des éléments

μ = (μ_1, \dots, μ_n) \in Z^n

tels que

|μ_i| ⩽ Nr/(n‖w⃗_i‖)

pour tout

i \in {1, \dots, n}

. Pour

μ \in M

, posons

p(μ) = \sum_(i = 1)^n μ_i x_i

et soit

P = {p(μ); μ \in M}

Démontrer les propriétés suivantes :
a) Si

μ

μ^'

sont deux éléments distincts de

M, p(μ)

p(μ^')

ne sont pas congrus modulo

N

.
b) Le cardinal de

P

est supérieur ou égal à

(r/n)^n(3/4)^(n(n - 1)/4)N

.
c) Pour tout

μ \in M

, la classe modulo

N

p(μ)

appartient à

ℬ(X, r)

.
3. Soit

X

une partie de

Z/NZ

de cardinal

n > 0

r

un nombre réel tel que

0 < r < 1/2

. Démontrer que

ℬ(X, r)

contient une progression arithmétique propre de dimension

n

et de taille au moins

(3/4)^(n(n - 1)/4)(r/n)^n N

.
4. Soit

A

une partie non vide de

Z/NZ

; soit

α

σ

des nombres réels strictement positifs tels que

Card(A) ⩾ αN

; on pose

σ = Card(A + A)/Card(A)

. Démontrer que 2A

2A

contient une progression arithmétique propre de dimension

d ⩽ 8σlog(1/α)

et de taille

⩾ N(128σlog(1/α)(4/3)^((d - 1)/4))^(- d)

V. Théorème de Freiman-Rusza-Chang

Soit

G

un groupe abélien, soit

A

une partie non vide de

G

. À partir de la question V.4, on pourra utiliser librement l'inégalité remarquable due à Plünnecke affirmant que pour tous entiers naturels

m

n, Card(mA - nA) ⩽ σ^(m + n)Card(A)

, où

σ = Card(A +

A) / Card(A).

Soit

H

un groupe abélien et soit

f

une application de

A

dans

H

. Si

k

est un entier

⩾

1 , on dit que

f

est

k

-tendue si l'on a

f(x_1) + \dots + f(x_k) = f(y_1) + \dots + f(x_k)

dès que

x_1, \dots, x_k, y_1, \dots, y_k

sont des éléments de

A

tels que

x_1 + \dots + x_k = y_1 + \dots + y_k

Soit

B

une partie non vide de

H

. On dit que

A

est

k

-semblable à

B

s'il existe des applications bijectives

f : A \to B

g : B \to A

inverses l'une de l'autre qui sont

k

-tendues.

Soit $G$ et $H$ des groupes abéliens, soit $k$ un entier naturel $⩾ 2$ , soit $A$ une partie de $G$ et soit $f : A \to H$ une application qui est $k$ -tendue. Soit $n$ et $m$ des entiers naturels tels que $1 ⩽ m + n ⩽ k$ .
a) Démontrer que pour tout entier $p$ tel que $1 ⩽ p ⩽ k$ , $f$ est $p$ -tendue.
b) Vérifier qu'il existe une unique application $F : mA - nA \to H$ telle que

F(a_1 + \dots + a_m - b_1 - \dots - b_n) = f(a_1) + \dots + f(a_m) - f(b_1) - \dots - f(b_n)

pour tout

(a_1, \dots, a_m, b_1, \dots, b_n) \in A^(m + n)

.
c) Si

p

est un entier naturel tel que

1 ⩽ p ⩽ k/(m + n)

, démontrer que

F

est

p

tendue.
d) On suppose que

A

est une progression arithmétique de dimension

d

det de taille

M

, pour des entiers naturels non nuls

d

M

. Démontrer qu'il en est de même de

f(A)

.
2. Soit

G

H

des groupes abéliens, soit

k

un entier naturel tel que

k ⩾ 2

. Soit

A

B

des parties finies non vides de

G

H

respectivement qui sont

k

-semblables.
a) Soit

m, n, p

des entiers naturels tels que

(m + n)p ⩽ k

. Démontrer que

mA - nA

mB - nB

sont

p

-semblables.
b) En déduire que

Card(mA - nA) = Card(mB - nB)

pour tout couple

(m, n)

d'entiers naturels tels que

m + n ⩽ k

.
3. Soit

N

un entier naturel ; soit

p

un nombre premier. Soit

f : Z/pZ \to Z

l'application qui, à

x \in Z/pZ

, associe l'unique entier de

{0, \dots, p - 1}

qui appartient à la classe de congruence

x

. Soit

k

un entier naturel tel que

k ⩾ 2

.
a) Pour

j \in {1, \dots, k}

, on note

I(j)

l'ensemble

[(j - 1)/kp, j/kp[ \cap N

. Démontrer que pour tout entier

j \in {1, \dots, k}

, la restriction de

f

f^(- 1)(I(j))

est une application

k

-tendue de

f^(- 1)(I(j))

dans

Z

.
b) Soit

A

une partie de

Z/pZ

. Démontrer que pour tout

u \in (Z/pZ)^*

, il existe une partie

A(u)

A

de cardinal

⩾ Card(A)/k

telle que l'application

f_u : A(u) \to Z/NZ

définie par

x \mapsto f(ux)(modN)

soit

k

-tendue.
c) Soit

z

un élément non nul de

kA - kA

; combien y a-t-il d'éléments

u \in (Z/pZ)^*

tels que

f(uz) \equiv 0(modN)

? En déduire que si

N ⩾ Card(kA - kA)

, il existe

u \in (Z/pZ)^*

tels que

A(u)

f_u(A(u))

soient

k

-semblables.
4. Soit

A

une partie finie de

Z

. On suppose que

A

est de cardinal au moins 2 et on pose

σ = Card(A + A)/Card(A)

.
a) Démontrer que

σ ⩾ 3/2

.
b) Soit

k

un entier naturel. Démontrer que pour tout nombre premier

p

assez grand,

A

est

k

-semblable à une partie de

Z/pZ

.
c) Soit

k

un entier naturel tel que

k ⩾ 2

. Démontrer que pour tout entier naturel

N

tel que

N > σ^(2k)Card(A)

, il existe une partie

B

A

de cardinal

⩾ Card(A)/k

qui est

k

semblable à une partie de

Z/NZ

.
d) En prenant

k = 8

et en choisissant pour

N

un nombre premier tel que

σ^(2k)Card(A) < N < 2σ^(2k)Card(A)

(on ne cherchera pas à démontrer l'existence d'un tel nombre premier

N

), démontrer l'énoncé suivant : il existe un nombre réel

c_1 > 0

(indépendant de

A

et de

σ

) tel que

2A - 2A

contienne une progression arithmétique propre de dimension au plus

c_1 σlogσ

et de taille au moins

Card(A)exp(- c_1 σ^2(logσ)^2)

.
5. Soit

A

une partie finie non vide de

Z

; on pose

σ = Card(A + A)/Card(A)

et on note

c

le plus petit entier naturel tel que

c ⩾ 2σ

. Soit

P

une progression arithmétique propre de dimension

d

et taille

βCard(A)

qui est contenue dans

2A - 2A

, où

β

est un nombre réel strictement positif.

On définit des suites

(P_i)

(S_i)

de parties de

Z

par récurrence comme suit:

on pose $P_0 = P$ ;
si $P_0, S_0, P_1, \dots, P_i$ sont définis, on considère une partie $S_i$ de $A$ de cardinal maximal de sorte que les parties $x + P_i$ , pour $x \in S_i$ , soient deux à deux disjointes;
si $Card(S_i) ⩽ c$ , on s'arrête;
si $Card(S_i) > c$ , on choisit une partie $S_i^'$ de $S_i$ dont le cardinal est égal à $c$ , on pose $P_(i + 1) = S_i^' + P_i$ et on continue.
a) Soit $t$ un entier tel que la partie $P_t$ soit définie. Démontrer que l'on a $Card(P_t) = c^t Card(P)$ . Démontrer que $P_t \subset (t + 2)A - 2A$ , et en déduire l'inégalité

2^t ⩽ σ^4 Card(A)/Card(P)

b) Soit

t

le plus grand entier tel que

P_t

soit définie. Démontrer l'inclusion

A \subset (P - P) + (S_0^' - S_0^') + \dots + (S_(t - 1)^' - S_(t - 1)^') + S_t.

c) Pour toute partie finie non vide

S

Z

, démontrer que

S - S

est contenue dans une progression arithmétique de dimension

Card(S)

et de taille

3^(Card(S))

. En déduire qu'il existe un nombre réel

c_2

(indépendant de

σ, β

d

) tel que que

A

soit contenu dans une progression arithmétique de dimension

δ

et de taille

τ

, avec

δ ⩽ c_2(d + σlogσ/β) et logτ/(Card(A)) ⩽ c_2(d + logσ/β)

Démontrer qu'il existe un nombre réel $c_3 > 0$ de sorte que l'énoncé suivant (théorème de Freiman-Rusza-Chang) soit vérifié : Soit $A$ une partie finie non vide de $Z$ et posons $σ = Card(A + A)/Card(A)$ ; alors, $A$ est contenue dans une progression arithmétique de dimension $δ$ et de taille $M$ , où

δ ⩽ c_3 σ^3(logσ)^2 et logM/(Card(A)) ⩽ c_3 σ^3(logσ)^2

Fin de l'épreuve.

Questions fréquentes

4 questions

Sur quels chapitres porte ce sujet de maths 1 des ENS MP 2009 ?

Il porte sur la combinatoire additive dans les groupes abéliens, les formes quadratiques sur les réseaux entiers et la transformation de Fourier discrète, combinées pour étudier les progressions arithmétiques.

Les parties du sujet sont-elles indépendantes ?

Les trois premières parties sont indépendantes entre elles ; leurs résultats sont ensuite combinés dans la partie IV, puis utilisés dans la partie V pour conclure.

Ce sujet demande-t-il de connaître la transformation de Fourier discrète ?

Oui, la partie III introduit et utilise la transformation de Fourier sur Z/NZ pour établir des propriétés des sommes de parties.

Quel est le résultat final démontré dans ce sujet ?

Le sujet démontre le théorème de Freiman-Ruzsa-Chang, qui affirme que toute partie finie non vide de Z est contenue dans une progression arithmétique de dimension et de taille contrôlées par le rapport Card(A+A)/Card(A).

Pas de description pour le moment

Commentaires• ENS Mathématiques 1 MP 2009

Connectez-vous pour participer aux discussions

Partagez vos avis, posez des questions et échangez avec la communauté

Chargement des commentaires...