\documentclass[a4paper,11pt]{article}
\usepackage[latin1]{inputenc}
\usepackage[T1]{fontenc}
\usepackage[francais]{babel}
\usepackage{graphicx}
\usepackage{tabls}
\usepackage{color}
\usepackage{array}
\usepackage{hyperref}
\title{Sur la conjecture d'Erdös-Straus}
\date{janvier 2010}
\author{Michel Mizony\\Institut C. Jordan (UMR CNRS) et IREM de Lyon, université Lyon 1}
\begin{document}
\maketitle

\tableofcontents
\newpage
\section{Sur la conjecture d'Erdös-Straus}
	\begin{center}
	\includegraphics[width=3cm]{tablettes}
	\end{center}
\subsection{Le problème}
L'énoncé ci-dessous est la conjecture d'Erdös et Straus. Plusieurs généralisations et problèmes ont été proposées depuis. La question de fond étant : \\ \og Quels rapports peut-on établir entre décompositions de fractions en somme de trois fractions égyptiennes et connaissance des nombres premiers? \fg {}  \\

\textbf{Toute fraction $\frac{4}{n}$ peut-elle s'écrire sous la forme :}
 $$\frac{1}{x}+\frac{1}{y}+\frac{1}{z}\ ?$$
\\
\\Existe-t-il une formule donnant une décomposition :
\\$$\frac{4}{n}=\frac{1}{x}+\frac{1}{y}+\frac{1}{z}\ ?$$
\\
\\Et pour deux entiers naturels $a$ et $b$, sous quelles conditions a-t-on :
$$\frac{a}{b}=\frac{1}{x}+\frac{1}{y}+\frac{1}{z}\ ?$$

 \subsubsection{Quelques étapes vers la résolution \dots}		
\begin{itemize}
 \item 1948, énoncé de la conjecture par Erdös et Straus
 \item 1969, les résultats de Mordell.
\item 1999, vérification de la conjecture pour $n<10^{14}$ par Swett.
\item 2000, le résultat négatif de Schinzel : pas de solution générale par une formule polynomiale.
\end{itemize}
\subsubsection{\dots~détaillées}

\textbf{Evidences :}  si $n$ vérifie la conjecture, $k\,n$ également. Si $n$ est premier et $\frac{4}{n}=\frac{1}{x}+\frac{1}{y}+\frac{1}{z}$, alors 1 ou 2 des trois nombres $x$, $y$ et $z$ sont divisibles par $p$.\\ 
Il existe une formule polynomiale pour $n=2$ modulo 3, une autre pour $n=3$ modulo 4, etc..\\
Il reste à démontrer la conjecture pour $n$ premier et égal à 1 modulo 24.\\

Un résultat de {\bf Mordell} : pour n premier,
\\si $\frac{4}{n}=\frac{1}{x}+\frac{1}{yn}+\frac{1}{zn}$, alors il existe 4 entiers $A$, $B$, $C$ et $D$, avec $A$, $B$, $C$ premiers entre eux deux à deux tels que $x=BCD$, $y=ABD$ et $z=ACD$.\\

En conséquence, il reste à démontrer la conjecture pour $n$ premier et égal à 1, 121, 169, 289, 361 et 529 modulo 840.	

\section{Une formule}
\begin{equation}
\frac{4}{n}=\frac{1}{m\,n}+\frac{4m-1}{m\,n+d}+\frac{(4m-1)d}{(m\,n+d)m\,n}.
\end{equation}  
Sans approfondir ici, il est clair que cette identité n'est pas tombée du ciel, mais est le fruit d'une grande quantité d'algorithmes mis en \oe uvre ayant deux buts :
\begin{enumerate}
\item être efficace : passer de 100 décompositions à la seconde à $20\,000$ n'est pas anodin.\\
\item être le plus proche possible d'une preuve avec papier et crayon, l'idée sous-jacente à ces algorithmes et formules ayant été d'éviter le plus possible le recours à la fonction {\it partie entière}.
\end{enumerate}
Il n'en reste pas moins vrai qu'il m'est difficile de préciser le long cheminement suivi et de dire pourquoi je l'ai écrite ce 13 Août 2009, et généralisée, ce qui m'était évident, dans l'heure qui suit :\\
Soient $a$ et $b$ deux entiers, alors pour tout couple d'entiers $m$ et $d$ on a l'identité : 
\begin{equation}\label{general}
\frac{a}{b}=\frac{1}{m\,b}+\frac{a\,m-1}{m\,b+d}+\frac{(a\,m-1)d}{(m\,b+d)b\,m}.
\end{equation}

 \subsection{Sur la formule (1)}
\textbf{Proposition :} Cette formule (1) est équivalente à celle de Mordell.\\
\begin{equation}
\frac{4}{n}=\frac{1}{BCD}+\frac{1}{ABD\,n}+\frac{1}{ACD\,n}.
\end{equation} 
 
Pour cela, en suivant une remarque d'un collègue, posons $m = ABD$ et $d = B^2D$ qui
divise $m^2$ dans cette équation.

Exprimons $A$ et $D$ en fonction de $m$, $d$, $B$ et $C$ :

$$\frac{4}{n}=\frac{B}{C\,d}+\frac{1}{m\,n}+\frac{B}{C\,m\,n},$$

qui se réduit à 
\begin{equation}
\frac{C\,d}{B}=\frac{m\,n+d}{4m-1}.
\end{equation}
Or $B$ divise $d=B^2D$, donc $\frac{m\,n+d}{4m-1}$ est un entier, cqfd.\\


\textbf{L'intérêt} principal de cette formule (1) qu'il faut lire sous la forme :
 $$\frac{4}{n}=\frac{1}{m\,n}+\frac{1}{\frac{m\,n+d}{4m-1}}+\frac{1}{\frac{(m\,n+d)\,m}{(4m-1)\,d}n} ,$$
est d'obtenir une décomposition de $\frac{4}{n}$ en somme de trois fractions égyptiennes sous la seule condition que $m\,n+d$ soit divisible par $4m-1$. D'où des algorithmes efficaces.
    
Un deuxième intérêt est de reformuler la conjecture d'Erdös-Straus sous la forme :

{\bf Conjecture 2 :} Pour tout nombre premier $p$ il existe un entier $m$ et un diviseur $d$ de $m^2$
tels que $m\,p+d$ soit divisible par $4m-1$.\\
La validité de cette conjecture (vérifiée en quelques minutes pour $p<10^9$) entraîne celle
d'Erdös-Straus.

Cette formulation établit de plus un lien étroit entre décompositions en somme de fractions égyptiennes et une propriété des nombres premiers. A ma connaissance, je n'ai rien remarqué dans la littérature, à propos de cette conjecture; cependant un rapport existe avec les nombres pentagonaux, cf. Sloane A144065 par exemple.\\
   
{\bf Retour sur le résultat de Schinzel}: cette identité (1) donne naissance à plusieurs formules polynômiales pour chaque $m$ et pour chaque $d$ diviseur de $m^2$, autrement dit à une infinité de formules polynômiales, ainsi, sans contredire ce résultat, on peut espérer prouver la conjecture. On peut exprimer les choses autrement en disant que cette infinité inévitable de formules donne une heuristique à ce résultat de Schinzel.\\

\subsection{La formule  (1) et  les nombres pentagonaux}
En considérant $m \in \{1,2,4\}$ la formule (1) permet de retrouver le résultat théorique donnant les 6 classes modulo 840 pour lesquelles la conjecture d'Erdös-Straus n'est pas démontrée; s'il l'on considère $m \in \{1,2,3,4,14\}$, alors il ne reste plus que 36 classes modulo $9240=11\times 840$, ce qui améliore beaucoup le résultat précédent (il faut comprendre 14 à travers le fait que $14*4-1$ est multiple de 11); etc. mais cette piste, très efficace au niveau algorithmique, s'avère vaine pour la preuve de l'existence.\\
Par contre 24 est le plus grand nombre pour lequel il n'existe plus qu'une seule classe à étudier. Soit donc les nombres de la forme $n=24k+1$ et considérons les nombres k pour lesquels il existe m et d (divisant $m^2$) donnant une décomposition de $\frac{4}{n}$, via cette formule (1). L'expérimentation sur ordinateur montre que ce sont les nombres non pentagonaux, autrement dit les
nombres k tels que n ne soit pas un carré. Une piste sérieuse qui conduit à la conjecture :\\ 


{\bf Conjecture 3 :} Pour tout nombre $k$ non pentagonal alors pour $n=24k+1$, il existe $m$ et $d$ divisant $m^2$ tels que $\frac{m\,n+d}{4m-1}$ soit un entier.\\
La validité de cette conjecture entraîne celle d'Erdös-Straus.

\subsection{On généralise la formule (1)}
Pour n admettant un facteur $r$, en particulier pour $n=24k+1$ où $k$ est un nombre pentagonal, il est pratique d'utiliser l'identité suivante qui généralise, pour $r=1$, l'identité de base :
\begin{equation}
\frac{4}{n}=\frac{1}{m\,n}+\frac{4m-1}{(m\frac{n}{r}+d)r}+\frac{(4m-1)d}{(m\frac{n}{r}+d)m\,n}.
\end{equation}
Evidemment cette formule donne une décomposition si $r$ divise $n$, $4m-1$ divise $m\frac{n}{r}+d$ et d divise $m^2$ et donne lieu à un algorithme récursif qui décompose toute fraction $\frac{4}{n}$.

\subsection{Pour une fraction $\frac{a}{b}$}
Prenons deux nombres a et b, alors on a l'identité :
\begin{equation}
\frac{a}{b}=\frac{1}{m\,b}+\frac{a\,m-1}{(m\frac{b}{r}+d)r}+\frac{(a\,m-1)d}{(m\frac{b}{r}+d)m\,b}.
\end{equation}
Cette formule donne une décomposition si $r$ divise $b$, $a\,m-1$ divise $m\frac{b}{r}+d$ et $d$ divise $m^2$ et donne lieu à un algorithme récursif qui décompose toute fraction $\frac{a}{b}$, sauf pour un nombre fini d'entre elles à a fixé, (c'est la conjecture la plus générale).

\section{Algorithmes}

Le principe algorithmique est basé sur les identités (1) et (5); il nécessite une initialisation qui construit l'ensemble des diviseurs $d$ de $m^2$. Nous donnons un programme général, écrit en "maple 9" qui fournit la décomposition des fractions $\frac{4}{n}$ en somme de trois fractions égyptiennes. On peut en déduire un algorithme encore plus rapide qui décompose les nombres de la forme $n=24k+1$. Ces algorithmes sont l'aboutissement d'une dizaine d'autres, toujours de plus en plus concis, théoriques et efficaces (et qui m'ont permis de mettre en évidence les identités).

Quelques tests laissent envisager que l'on peut battre rapidement le record d'Allan Swett.



\subsection{Un programme de décomposition}

> with(numtheory):Dm:=[seq(divisors($m^2$),m=1..3500)]:\textcolor{red}{\#initialisation}

> ErdosStraus:=proc(p)\par
local m, d, c;
global Dm;\par
\hspace{0.4cm}    for m to 3500 do \textcolor{red}{\#début du corps du programme}\par
\hspace{0.8cm}        if $1 < m$ and p mod m = 0 then\par
\hspace{1.2cm}            return([p, m, ErdosStraus(p/m)])
                      end if;\textcolor{red}{\# récursivité} \par
\hspace{0.8cm}        for d in Dm[m] do\par
\hspace{1.2cm}            if (m*p + d) mod (4*m - 1) = 0 then\par
\hspace{1.6cm}                c := (m*p + d)/(4*m - 1);\par
\hspace{1.6cm}                return([p, [m*p, c, c*m*p/d], [m, d]])
                      end if\par
\hspace{0.8cm}        end do;\par
\hspace{0.4cm}    end do;\textcolor{red}{\#fin du corps du programme}\par
\hspace{0.4cm}    m:=sqrt(p);\textcolor{red}{\# pour les nombres pentagonaux restants}\par
\hspace{0.4cm}    if is(m, integer) then return([p, m, ErdosStraus(m)])
                  end if;\par
\hspace{0.4cm}    return(p = echec)\par
end proc:

ErdosStraus(3361);
               [3361, [84025, 850, 571370], [25, 125]]
               
ErdosStraus(2031121);

      [2031121, [1267419504, 507984, 1117758384236], [624, 576]]

\subsection{Pour les entiers de la forme $24k+1$}
Soit $p$ un nombre de la forme $24k+1$ et $m$ et $d$ (diviseur de $m^2$); dire que $mp+d =0$ modulo ($4m-1$) équivaut à dire que $k$ appartient à un certain ensemble que l'on notera $R[m]$ dans $Z/(4m-1)Z$. Voici une procédure permettant de construire facilement ces ensembles $R[m$]. La conjecture d'Erdös-Straus est vraie si les ensembles $K[m]=\{k/\,k\ modulo\ (4m-1) \in R[m]\}$ recouvrent le complémentaire des nombres pentagonaux.


> construitRm24:=proc(m)\par
  local v,d;global Dm;\par
  map(v->op(2,op(v)),\{seq(msolve((24*k+1)*m+d=0,4*m-1),d=Dm[m])\});\par
  end:\par
> R:=[seq(construitRm24(m),m=1..1000)]:\par
> R[1..6];\par
  [\{\}, \{3, 4, 6\}, \{3, 9, 10\}, \{3, 4, 8, 9, 13, 14\}, \{11, 14, 18\},
        \{6, 9, 10, 14, 16, 18, 19, 20, 21\}]

A partir de là on construit un algorithme encore plus efficace pour donner une décomposition en somme en trois fractions égyptiennes de la fraction $\frac{4}{24k+1}$. En particulier pour tout premier inférieur à $10^{11}$, on obtient un $m$ inférieur à 1000. Mais
$m=2295$ pour

ErdosStraus(240000095140208881);

[240000095140208881, [550800218346779381895, 60006560447410326,

 72007901082075867184856155781526030], [2295, 459]]

\section{Le contexte : EXPRIME}

EXpérimenter des PRoblèmes Innovants en Mathématiques à l'\'Ecole

\textcolor{red}{http://educmath.inrp.fr/Educmath/ressources/documents/exprime/}
	
		Les documents présentés par ce groupe sont issus d'une recherche en cours, menée conjointement par l'INRP, l'IREM, le LEPS LIRDHIST  (Université Claude Bernard Lyon 1) et l'IUFM de Lyon et dont le coeur est l'étude de la dimension expérimentale dans les problèmes de recherche. Nous nous attachons dans cette présentation à montrer les résultats de la recherche en nous appuyant sur les observations de classes dans des situations de recherche de problèmes.

  
\textbf{Contexte et question de recherche} : De nombreuses expériences ont eu lieu depuis près de vingt ans tant au collège, qu'à l'école élémentaire et au lycée, concernant la mise en oeuvre de problèmes de recherche en mathématiques dans différents contextes. Elles montrent clairement les apports en termes d'apprentissage de la démarche scientifique : développement d'heuristique, élaboration de conjectures, mobilisation d'outils de contrôle et de validation etc., elles montrent aussi la possibilité d'insérer des situations de ce type en classe.

{\it Or une des sept situations robustes présentées concerne la décomposition de 1 en somme de fractions égyptiennes. Une des situations connexes à ce problème est la conjecture de Erdös et Straus que Marie-Line nous a exposée en Février 2009. Ce fut pour moi le début d'une recherche active.}

\subsection{Sur l'expérimentation en classe}
Cette expérimentation est menée en classe de terminale scientifique par Marie-Line Gardes depuis plus d'un an, suivant la méthode de la résolution d'un problème ouvert.
 
L'énoncé est la conjecture d'Erdös-Straus : {\it Pour tout n entier naturel, peut-on trouver trois entiers naturels a, b, c tels que $\frac{4}{n}=\frac{1}{a}+\frac{1}{b}+\frac{1}{c}$.}

Les observations portent essentiellement d'une part sur {\bf la dévolution} du problème par les élèves (conditions pour que le problème ne soit plus le problème du professeur mais devienne celui des élèves), et d'autre part sur {\bf le caractère expérimental} de ce problème (qui passe par le va-et-vient entre expériences et théorie).

Un bilan de cette recherche, en cours de rédaction, est fait par Marie-Line qui a rejoint notre groupe EXPRIME; des résultats préliminaires on déjà fait l'objet d'un mémoire de Master 2 HPDS à l'université Lyon1 en juin 2009 sous le titre : {\it Etude du processus de recherche d'élèves de terminale scientifique confrontés à la résolution d'un problème ouvert en arithmétique}.




\section{Conclusion}
C'est en recherchant des algorithmes de plus en plus efficaces et en cherchant à se passer de la fonction partie entière que petit à petit a émergé l'identité. Mais celle-ci ne semble pas permettre de pouvoir montrer facilement l'existence et donc la conjecture. Il est important de signaler que j'ai volontairement mené cette recherche sans essayer d'avoir recours à la littérature
existente que je n'ai examinée qu'une fois l'identité établie. 

Par ailleurs, à l'instar des babyloniens (cf. la photo de tablettes datant de 4300 ans environ), j'ai plus été intéressé par la construction d'algorithmes mathématiques que par l'élaboration de preuves.

Puisse cette {\it narration de recherche} éclairer un peu des liens qui existent entre l'algorithmie, discipline à part entière avec ses multiples facettes, et les mathématiques; on peut en particulier penser à un aspect expérimental qui se développe sur des bases algorithmiques. 

\section{Bibliographie}
 
Aldon, G.  Cahuet, P.-Y.,  Durand-Guerrier, V.,  Front, M.,  Krieger, D.,  Mizony, M. et  Tardy, C. (à paraître). Expérimenter des problèmes de recherche innovants en mathématiques à l'école. INRP.

Guy R. Unsolved Problems in Number Theory, 3ème édition, Springer, 2003, problème D11, pp 252-262.

Mordell L.J. Diophantine equations, London, New York : Academic press, 1969, chapter 30.

Schinzel A.  On sums of three unit fractions with polynomial denominators. Funct. Approx. Comment. Math. 28 : 187-194, 2000.

page Internet d'Allan Swett : http://math.uindy.edu/swett/esc.htm.

page Internet Sloane : http://www.research.att.com/~njas/sequences/A144065.\\

\end{document}