Théorème de Beatty

Le théorème de Beatty est un théorème d'arithmétique publié en 1926 par le mathématicien canadien Samuel Beatty (mais déjà mentionné par Lord Rayleigh en 1894) qui donne une condition nécessaire et suffisante sur deux réels pour que les deux suites de Beatty associées partitionnent ℕ*.

Énoncé

Il affirme l'équivalence des deux points suivants, pour deux nombres réels p {\displaystyle p} et q {\displaystyle q} strictement positifs :

  • Les nombres p {\displaystyle p} et q {\displaystyle q} sont irrationnels et vérifient 1 p + 1 q = 1. {\displaystyle {\frac {1}{p}}+{\frac {1}{q}}=1.}
  • Les deux suites d'entiers P = ( E ( n p ) ) n ∈ N ∗ {\displaystyle P=(\mathrm {E} (np))_{n\in \mathbb {N} ^{*}}} et Q = ( E ( n q ) ) n ∈ N ∗ {\displaystyle Q=(\mathrm {E} (nq))_{n\in \mathbb {N} ^{*}}} , dites « suites de Beatty », forment une partition de l'ensemble ℕ*[1].

Ici, la fonction E désigne la fonction partie entière.

Démonstration
  • On suppose que les suites P et Q forment une partition de ℕ*.
    • Les ensembles { E ( n α ) ∣ n ∈ N ∗ } {\displaystyle \{E(n\alpha )\mid n\in \mathbb {N} ^{*}\}} où α {\displaystyle \alpha } est un réel positif ont comme densité asymptotique 1 α {\displaystyle {\frac {1}{\alpha }}} . Les supports des suites P et Q forment une partition de ℕ*, donc la somme de leurs densités vaut 1 :
    1 p + 1 q = 1 {\displaystyle {\frac {1}{p}}+{\frac {1}{q}}=1} .
    • De plus, p et q ne peuvent être tous les deux rationnels, car si c'est le cas p = a 1 b 1 , q = a 2 b 2 {\displaystyle p={\frac {a_{1}}{b_{1}}},q={\frac {a_{2}}{b_{2}}}} , alors E ( b 1 a 2 p ) = E ( b 2 a 1 q ) ( = a 1 a 2 ) {\displaystyle E(b_{1}a_{2}p)=E(b_{2}a_{1}q)(=a_{1}a_{2})} . Or les suites P et Q n'ont aucun élément en commun. L'un des deux est irrationnel, et par suite les deux sont irrationnels (car p − 1 + q − 1 = 1 {\displaystyle p^{-1}+q^{-1}=1} )
  • Réciproquement, supposons que p et q sont irrationnels et p − 1 + q − 1 = 1 {\displaystyle p^{-1}+q^{-1}=1} . Fixons un entier k ≥ 1 et notons n (resp. m) le nombre de termes de la suite P (resp. Q) qui sont inférieurs ou égaux à k. Alors,
    n = E ( ( k + 1 ) / p ) {\displaystyle n=\mathrm {E} ((k+1)/p)} et m = E ( ( k + 1 ) / q ) {\displaystyle m=\mathrm {E} ((k+1)/q)} .
    Par définition de la partie entière et par irrationalité de p et q, nous avons les inégalités suivantes :
    k + 1 p − 1 < n < k + 1 p {\displaystyle {\frac {k+1}{p}}-1<n<{\frac {k+1}{p}}} et k + 1 q − 1 < m < k + 1 q {\displaystyle {\frac {k+1}{q}}-1<m<{\frac {k+1}{q}}}
    donc k − 1 < n + m < k + 1 {\displaystyle k-1<n+m<k+1} , autrement dit
    n + m = k {\displaystyle n+m=k} .
    De même, les nombres n' et m' de termes de P et Q qui sont inférieurs ou égaux à k – 1 vérifient :
    n ′ + m ′ = k − 1 {\displaystyle n'+m'=k-1} .
    Par conséquent, le nombre de termes de P égaux à k plus le nombre de termes de Q égaux à k vaut :
    n − n ′ + m − m ′ = k − ( k − 1 ) = 1 {\displaystyle n-n'+m-m'=k-(k-1)=1} ,
    c'est-à-dire que l'entier k appartient bien à une et une seule des deux suites.

Ce résultat ne se généralise pas : il est impossible de partitionner ℕ* avec trois suites ou plus de cette forme[2]. Une question plus générale est la conjecture de Fraenkel[3].

Exemple

L'un des premiers exemples connus a été découvert dès 1907 par le mathématicien néerlandais Wythoff, indépendamment du théorème de Beatty. Pour φ {\displaystyle \varphi } le nombre d'or, nous avons :

1 φ + 1 φ 2 = 1 . {\displaystyle {\frac {1}{\varphi }}+{\frac {1}{\varphi ^{2}}}=1\,.}

Les deux suites obtenues sont alors :

  • E ( n φ ) {\displaystyle {\rm {E}}(n\varphi )} , n > 0 : 1, 3, 4, 6, 8, 9, 11, 12, 14, 16, 17, 19, 21, 22, 24, 25, 27, 29, ... suite A000201 de l'OEIS
  • E ( n φ 2 ) {\displaystyle {\rm {E}}(n\varphi ^{2})} , n > 0 : 2, 5, 7, 10, 13, 15, 18, 20, 23, 26, 28, 31, 34, 36, 39, 41, 44, 47, ... suite A001950 de l'OEIS

Les couples ( E ( n φ ) , E ( n φ 2 ) ) {\displaystyle ({\rm {E}}(n\varphi ),{\rm {E}}(n\varphi ^{2}))} apparaissent dans la résolution du jeu de Wythoff et caractérisent les positions à partir desquelles le joueur qui a le trait ne peut pas gagner.

Références

  1. ↑ Voir par exemple (en) Ivan Morton Niven, Diophantine Approximations, Dover, (1re éd. 1963) (lire en ligne), p. 34 (Theorem 3.7) ou (en) Aviezri Fraenkel, « Complementary systems of integers », Amer. Math. Monthly, vol. 84, no 2,‎ , p. 114-115 (lire en ligne).
  2. ↑ Voir par exemple Niven 2008 (Theorem 3.14), Fraenkel 1977 ou (en) R. L. Graham, « Complementary systems of integers », Amer. Math. Monthly, vol. 70, no 4,‎ , p. 407-409 (lire en ligne).
  3. ↑ (en) Robert Tijdeman, « Fraenkel's conjecture for six sequences », Discrete Math., vol. 222,‎ , p. 223-234 (lire en ligne).

Voir aussi

Articles connexes

Liens externes

  • Pages contenant des applets pour calculer les termes de la suite de Beatty, ou pour déterminer p et q en fonction des termes de la suite
  • Gilbert Julia, « Ecrit 2, CAPES Mathématiques : Suites de Beatty. Théorème de Beatty. Jeu de Wythoff (énoncé et éléments de correction) »,
  • (en) Eric W. Weisstein, « Beatty Sequence », sur MathWorld
  • (en) Alexander Bogomolny (en), « Beatty Sequences », sur Cut The Knot

Ouvrages

  • Serge Francinou, Hervé Gianella et Serge Nicolas, Exercices de mathématiques, oraux X-ENS. Algèbre 1, Cassini
  • (en) Ross Honsberger (en), Ingenuity in Mathematics, MAA, , « Essay 12: Complementary Sequences », p. 93-110
  • icône décorative Arithmétique et théorie des nombres