Bonsoir la compagnie. J'espère que tout se passe bien pour tous.
J'ai pour ce problème une idée. Je pense sauf erreur que pour $n = |A| = 3$ ou $n |A| = 4$, l'égalité $|A + A| = 2n - 1$ est possible: il faudra seulement que $\{a_{1}, a_{2}, a_{3}\}$ ou $\{a_{1}, a_{2}, a_{3}, a_{4}\}$ suive une progression arithmétique.
Mais plus généralement pour que cette égalité ($|A + A| = 2n - 1$) soit possible, il faudrait qu'en plus du fait que $\{a_{1}, a_{2}, \cdots, a_{n}\}$ doit suivre une progression arithmétique, que $\dfrac{\dfrac{n(n + 1)}{2} - 4}{2}$ soit pair (sinon $|A + A| = 2n$).
En fait, c'est un théorème fondamentale de la combinatoire additive:
Soit $A$ et $B$ deux ensembles finis non-vides des entiers (ou rationnels, réels ...), alors
\[|A+B|\geq |A|+|B|-1,\]
avec égalité si et seulement si l'un des deux ensembles est un singleton ou les deux sont des progressions artihmétiques de même raison.
En effet, si tu notes $A=\{a_1,a_2,\dots,a_d\}$, avec $a_1<a_2<\dots<a_d$ et $B=\{b_1,b_2,\dots,b_\ell\}$, avec $b_1<b_2<\dots<b_\ell$.
Tu as par compatibilité de la relation d'ordre:
\[a_1+b_1<a_2+b_1<\dots<a_{d-1}+b_1<a_d+b_1<a_d+b_2<\dots<a_d+b_\ell.\]
C'est une suite strictement croissante de $d+\ell-1$ éléments de $A+B$, ce qui donne l'inégalité.
De plus, dans le cas où $|A+B|=|A|+|B|-1$ et si $d$ et $\ell$ valent au moins $2$, on a encore $d+\ell-1$ éléments:
\[\begin{array}{rrrrrrrr}
a_1+b_1< & a_2+b_1< & \dots< & a_d+b_1< & a_d+b_2< & \dots< & a_d+b_{\ell-1}< & a_d+b_\ell\\
a_1+b_1< & a_1+b_2< & \dots< & a_{d-1}+b_2< & a_{d-1}+b_3< & \dots< & a_{d-1}+b_\ell< & a_d+b_\ell\end{array}\]Ils s'agit donc de la même suite d'éléments et on peut donner les égalités:
\[a_i-a_{i-1}=b_2-b_1,\ i\in[2,d].\ \textrm{et}\]
\[a_d-a_{d-1}=b_j-b_{j-1},\ j\in[2,\ell].\]
Cela permet de conclure que $A$ et $B$ sont des progressions arithmétiques de même raison ($r=a_d-a_{d-1}=b_2-b_1$).
Il n'y a par contre pas de souci dans l'autre sens, si $A$ et $B$ sont des progressions arithmétiques de même raison:
\[A=\{a_0+(i-1)r\mid i=1\dots d\}\ \textrm{et}\ B=\{b_0+(i-1)r\mid i=1\dots \ell\}\]
alors $A+B=\{a_0+b_0+(i-1)r\mid i=1\dots d+\ell-1\}$ et est de cardinal $d+\ell-1$, sans autre condition.
Dans $\mathbb{Z}/p\mathbb{Z}$, une telle inégalité est encore valable ($|A+B|\geq\min\{p,|A|+|B|-1\}$), mais est un peu plus subtile, car il n'y a pas de relation d'ordre compatible avec l'addition, c'est le théorème de Cauchy-Davenport. Le cas d'égalité est encore valable aussi (à une autre subtilité près), c'est le théorème de Vosper. Il y a beaucoup de généralisations de ces résultats, c'est un domaine de recherche actif et intéressant. (Je suis pas très objectif !!)
Soit $P$ un polynôme à coefficients 0 ou 1 et soit $A$ et $B$ deux polynômes tels que $AB=P,$ tels que $A$ et $B$ soient à coefficients positifs et soient moniques (càd de coefficient 1 pour leur terme de plus haut degré). On peut conjecturer qu'alors $A$ et $B$ sont aussi à coefficients $0$ ou $1$, et c'est vrai si $P$ est un polynôme réciproque (càd $P(x)=x^dP(1/x)$). Pour cela on adapte la methode de Krasner et Ranulac (CRAS 1937 ?).
Du point de vue des probabilités cette conjecture revient à dire que toute loi uniforme sur une partie finie des entiers n'est factorisable au sens de la convolution que par des lois uniformes.
Question donc : as-tu des idées sur ce vieux probleme ?
Réponses
Je me doutais bien que l'un d'entre vous aurait une réf à me donner.
J'ai pour ce problème une idée. Je pense sauf erreur que pour $n = |A| = 3$ ou $n |A| = 4$, l'égalité $|A + A| = 2n - 1$ est possible: il faudra seulement que $\{a_{1}, a_{2}, a_{3}\}$ ou $\{a_{1}, a_{2}, a_{3}, a_{4}\}$ suive une progression arithmétique.
Mais plus généralement pour que cette égalité ($|A + A| = 2n - 1$) soit possible, il faudrait qu'en plus du fait que $\{a_{1}, a_{2}, \cdots, a_{n}\}$ doit suivre une progression arithmétique, que $\dfrac{\dfrac{n(n + 1)}{2} - 4}{2}$ soit pair (sinon $|A + A| = 2n$).
Cordialement.
En fait, c'est un théorème fondamentale de la combinatoire additive:
Soit $A$ et $B$ deux ensembles finis non-vides des entiers (ou rationnels, réels ...), alors
\[|A+B|\geq |A|+|B|-1,\]
avec égalité si et seulement si l'un des deux ensembles est un singleton ou les deux sont des progressions artihmétiques de même raison.
En effet, si tu notes $A=\{a_1,a_2,\dots,a_d\}$, avec $a_1<a_2<\dots<a_d$ et $B=\{b_1,b_2,\dots,b_\ell\}$, avec $b_1<b_2<\dots<b_\ell$.
Tu as par compatibilité de la relation d'ordre:
\[a_1+b_1<a_2+b_1<\dots<a_{d-1}+b_1<a_d+b_1<a_d+b_2<\dots<a_d+b_\ell.\]
C'est une suite strictement croissante de $d+\ell-1$ éléments de $A+B$, ce qui donne l'inégalité.
De plus, dans le cas où $|A+B|=|A|+|B|-1$ et si $d$ et $\ell$ valent au moins $2$, on a encore $d+\ell-1$ éléments:
\[\begin{array}{rrrrrrrr}
a_1+b_1< & a_2+b_1< & \dots< & a_d+b_1< & a_d+b_2< & \dots< & a_d+b_{\ell-1}< & a_d+b_\ell\\
a_1+b_1< & a_1+b_2< & \dots< & a_{d-1}+b_2< & a_{d-1}+b_3< & \dots< & a_{d-1}+b_\ell< & a_d+b_\ell\end{array}\]Ils s'agit donc de la même suite d'éléments et on peut donner les égalités:
\[a_i-a_{i-1}=b_2-b_1,\ i\in[2,d].\ \textrm{et}\]
\[a_d-a_{d-1}=b_j-b_{j-1},\ j\in[2,\ell].\]
Cela permet de conclure que $A$ et $B$ sont des progressions arithmétiques de même raison ($r=a_d-a_{d-1}=b_2-b_1$).
Il n'y a par contre pas de souci dans l'autre sens, si $A$ et $B$ sont des progressions arithmétiques de même raison:
\[A=\{a_0+(i-1)r\mid i=1\dots d\}\ \textrm{et}\ B=\{b_0+(i-1)r\mid i=1\dots \ell\}\]
alors $A+B=\{a_0+b_0+(i-1)r\mid i=1\dots d+\ell-1\}$ et est de cardinal $d+\ell-1$, sans autre condition.
Dans $\mathbb{Z}/p\mathbb{Z}$, une telle inégalité est encore valable ($|A+B|\geq\min\{p,|A|+|B|-1\}$), mais est un peu plus subtile, car il n'y a pas de relation d'ordre compatible avec l'addition, c'est le théorème de Cauchy-Davenport. Le cas d'égalité est encore valable aussi (à une autre subtilité près), c'est le théorème de Vosper. Il y a beaucoup de généralisations de ces résultats, c'est un domaine de recherche actif et intéressant. (Je suis pas très objectif !!)
Cordialement,
Le p'tit bonhomme
Soit $P$ un polynôme à coefficients 0 ou 1 et soit $A$ et $B$ deux polynômes tels que $AB=P,$ tels que $A$ et $B$ soient à coefficients positifs et soient moniques (càd de coefficient 1 pour leur terme de plus haut degré). On peut conjecturer qu'alors $A$ et $B$ sont aussi à coefficients $0$ ou $1$, et c'est vrai si $P$ est un polynôme réciproque (càd $P(x)=x^dP(1/x)$). Pour cela on adapte la methode de Krasner et Ranulac (CRAS 1937 ?).
Du point de vue des probabilités cette conjecture revient à dire que toute loi uniforme sur une partie finie des entiers n'est factorisable au sens de la convolution que par des lois uniformes.
Question donc : as-tu des idées sur ce vieux probleme ?