Pensez à lire la Charte avant de poster !

$\newcommand{\K}{\mathbf K}$


Les-Mathematiques.net - Cours de mathématiques supérieures
 Les-Mathematiques.net - Cours de mathématiques universitaires - Forum - Cours à télécharger

A lire
Deug/Prépa
Licence
Agrégation
A télécharger
Télécharger
136 personne(s) sur le site en ce moment
E. Cartan
A lire
Articles
Math/Infos
Récréation
A télécharger
Télécharger
Théorème de Cantor-Bernstein
Théo. Sylow
Théo. Ascoli
Théo. Baire
Loi forte grd nbre
Nains magiques
 
 
 
 
 

Nombre de triplets solutions de $px+qy+pqz=n$

Envoyé par zem 
zem
Nombre de triplets solutions de $px+qy+pqz=n$
il y a trois semaines
Nombre de triplets solutions de $px+qy+pqz=n$

Bonjour
Auriez-vous des idées pour aborder le problème ci-dessus dans $\mathbb N$ avec $p$ et $q$ premier entre eux.
Merci.



Edité 1 fois. La dernière correction date de il y a trois semaines et a été effectuée par AD.
Re: Nombre de triplets solutions de $px+qy+pqz=n$
il y a trois semaines
Si on est pressé, le mieux est d'utiliser les dénumérants. Si $D_3(n)$ désigne le dénumérant cherché, alors
$$D_3 (n) = \sum_{j=0}^{\frac{n}{pq}} D_2(n-jpq) = \sum_{j=0}^{\frac{n}{pq}} \left( \frac{n}{pq} - j + r_j \right)$$
où $r_j = 0$ ou $1$ selon une règle assez compliquée. On en déduit
$$D_3(n) = \left \lfloor \frac{n}{2pq} \right \rfloor \left( \left \lfloor \frac{n}{2pq} \right \rfloor + 1 \right) + O \left( \frac{n}{pq} \right).$$
zem
Re: Nombre de triplets solutions de $px+qy+pqz=n$
il y a trois semaines
Si je comprends bien c'est une approximation.
Pensez vous qu'une formule exacte serait envisageable ?
Re: Nombre de triplets solutions de $px+qy+pqz=n$
il y a trois semaines
C'est une formule avec terme principal et terme d'erreur.

Il existe des formules exactes, bien que souvent plus difficiles à établir (j'ai déjà donné des références sur ce forum). Par exemple, si tu aimes les formules un peu lourdes à manipuler
$$D_3(n) = \sum_{i=0}^{\lfloor n/p \rfloor} \sum_{j=0}^{\lfloor (n-ip)/q \rfloor} I(i,j)$$

$$I(i,j) := \begin{cases} 1, & \textrm{si } pq \mid n-pi-qj ; \\ 0, & \textrm{sinon}. \end{cases}$$

Autre méthode. La fonction génératrice de $D_3(n)$ est donnée formellement par
$$F(t) = \frac{1}{(1-t^p)(1-t^q)(1-t^{pq})}.$$
La méthode classique consiste alors à décomposer $F(t)$ en éléments simples, puis identifier le coefficient de $t^n$ pour déterminer $D_3(n)$. Cette méthode est toutefois assez peu utilisée en pratique, les calculs étant souvent bien longs. Elle est généralement réservée pour l'obtention de formules asymptotiques pour les dénumérants.
zem
Re: Nombre de triplets solutions de $px+qy+pqz=n$
il y a trois semaines
Merci.
Il est donc a priori difficile d'obtenir une formule simple et utilisable rapidement pour obtenir le nombre de solutions.
Re: Nombre de triplets solutions de $px+qy+pqz=n$
il y a trois semaines
Il me semble que Eugène Ehrhart a donné des méthodes pour ce genre de dénombrement, mais je n'ai pas ça sous le coude pour le moment.
Re: Nombre de triplets solutions de $px+qy+pqz=n$
il y a deux semaines
@Zem
Deux ou trois petites choses ; je ne sais pas si elles vont faire avancer le schmilblick. D'abord, c'est pas bien, mais je vais changer tes notations en $ax + by + abz = n$ avec $a, b \in \N^*$ premiers entre eux. Il est entendu que $x, y, z \in \N$. Je note $u_n$ le nombre de solutions.

1) Il y a un quasi-polynôme (ou polynôme périodique) de longueur $ab$, i.e. une famille de $ab$ polynômes :
$$
(P_0, P_1, \cdots, P_{ab-1})
\qquad \hbox {qui vérifie} \qquad
u_n = P_{n\ \bmod\ ab} \left( \left\lfloor {n \over ab} \right\rfloor \right) \qquad (\star)
$$
Ce qui veut dire que si $n \equiv 0 \bmod ab$, on prend $P_0$, $n \equiv 1 \bmod ab$, on prend $P_1$ and so on. Dans $(\star)$, le fait de diviser par $ab$ n'est pas standard : je m'aligne sur Gavin Brown & Alexander Kasprzyk (Convex Polytopes and Polyhedra).

2) Je vais expliciter ces polynômes. A cet effet, j'ai besoin d'introduire le semi-groupe $a\N + b\N$, à complémentaire fini. Je note $G$ ce complémentaire i.e. $G = \N \setminus (a\N + b\N)$, ensemble des gaps (trous) de $a\N + b\N$. Les résultats suivants sont ultra-classiques :
$$
g := \#G = {(a-1)(b-1) \over 2} , \qquad \qquad
\hbox {$2g-1 = (a-1)(b-1)-1$ est le plus grand gap}
$$
A droite, cela veut donc dire que $[2g, \infty[ \subset a\N + b\N$ i.e. qu'à partir de $2g$ tout le monde rentre dans le semi-groupe. Mais pas $2g-1$.

Il y a d'autres propriétés remarquables de $a\N + b\N$ : c'est un semi-groupe dit symétrique au sens où l'involution $x \mapsto (2g-1)-x$ de l'intervalle $[0.. 2g-1]$ échange les gaps et les non-gaps.

3) Il y a deux types de polynômes $P_i$ liés au polynôme binomial $B_2$ :
$$
B_2(X) = \binom {X}{2} = {X(X-1), \over 2}
$$
Et l'on a :
$$
P_i(X) = \cases {B_2(X+1) &si $i$ est un gap\cr B_2(X+2) & sinon }
$$

4) Ce qu'il faut savoir, c'est que lorsque l'on compte le nombre $v_n$ de solutions de $ax + by = n$, le semi-groupe $a\N + b\N$ intervient également. Et on a le même type de résultat pour le quasi-polynôme (il est de longueur $ab$) sauf qu'il faut remplacer d'une part $B_2$ par $B_1(X) = X$ et d'autre part translater la variable $X$ autrement : $B_1(X)$ si $i$ est un gap et $B_1(X+1)$ sinon.

5) Peut-on espérer un lien entre les suites $(u_n)_{n \ge 0}$ pour $ax + by + abz = n$ et $(v_n)_{n \ge 0}$ pour $ax + by = n$ ? Aucune idée.
Re: Nombre de triplets solutions de $px+qy+pqz=n$
il y a deux semaines
@Zem
Voici une formule close. Je note $f_{a,b}(n)$ la formule de Popoviciu pour $ax + by = n$ i.e. le nombre $v_n$ de solutions en conservant les notations de mon post précédent. Alors le nombre $u_n$ de solutions de $ax + by + abz = n$ est donné par :
$$
u_n = \left( \left\lfloor {n \over ab}\right\rfloor + 1\right) \times f_{a,b}(n) -
\binom {\left\lfloor {n \over ab}\right\rfloor + 1}{2}
$$
Re: Nombre de triplets solutions de $px+qy+pqz=n$
il y a deux semaines
@Claude Quitté : oui, c'est ce que j'ai fait dans mon premier message (i.e. se ramener au cas de deux inconnues, puis exploiter l'une ou l'autre des formules connues -- il n'y a d'ailleurs pas que celle de Popoviciu, il y a aussi Tripathi, Shiu; etc).

Le vrai problème réside dans la sommation des termes secondaires (notés $r_j$ dans mon message) de ces formules, sommation hautement non triiviale.

Quant aux polynômes d'Ehrhart évoqués par Chaurien, s'ils sont théoriquement remarquables, ils sont difficiles à mettre en œuvre en pratique.
Re: Nombre de triplets solutions de $px+qy+pqz=n$
il y a deux semaines
@noix de totos
Quand tu dis ``Oui, c'est que j'ai fait dans mon premier message'', cela veut dire que la formule que j'ai donnée dans
[www.les-mathematiques.net] figure dans ton premier message ? Tu y parles de $r_j = 0, 1$ selon une règle compliquée. Jamais eu de $r_j$, ni dans ma formule ni sur mon brouillon. Et d'ailleurs dans ton dernier post, tu parles de nouveau de sommation compliquée de termes secondaires. Et en passant, la formule de Popoviciu (les autres, je ne connais pas) n'a rien à voir avec mes affaires. J'aurais pu écrire mon résultat sous la forme (cf les notations dans mon post) :
$$
u_n = \left( \left\lfloor {n \over ab}\right\rfloor + 1\right) \times v_n - \binom {\left\lfloor {n \over ab}\right\rfloor + 1}{2} \qquad\qquad (\heartsuit)
$$
Si j'ai parlé de Popoviciu (que j'ai eu du mal à retrouver, ce n'est absolument pas ma spécialité, cela date de l'époque AlKashi), c'est juste allusion à une formule close.

J'ai procédé en utilisant le côté quasi-polynomial évoqué dans mon post [www.les-mathematiques.net] (où je dis explicitement dans le point 5. que je ne vois PAS le lien entre $v_n$ et $u_n$ !). Puis j'ai réfléchi à cet aspect quasi-polynômes de $u_\bullet$, $v_\bullet$, de même longueur $ab$ et de ``même bascule'' (gouvernée par les gaps de $a\N + b\N$). En fait, l'aspect quantitatif (polynômes binomiaux), on s'en fiche, ce qui compte c'est l'aspect qualitatif. Ce qui finit par donner $v_{n+kab} = v_n + k$. Et d'autres bricoles que je passe sous silence. ..Etc..

Et donc contrairement à ce que je disais dans le point 5, il y a bien un lien entre $u_\bullet$ et $v_\bullet$, celui donné par $(\heartsuit)$. Une fois au point sur mon brouillon, je me suis dit que cela faisait longtemps que je n'avais pas fait de programmation sur les polytopes (et un $+1$ quelque part dans une expression est si vite oublié). Cela ne peut pas faire de mal le Dimanche matin de faire joujou avec les polynômes d'Ehrhart et les polytopes. Et le bilan, c'est que l'expérimenation colle à la théorie.

Voilà, voilà. Je n'y connais pas grand chose et juste voulu voir (je me demande quand même si ce n'était pas de ma part un alibi pour faire de la programmation en dimension 3 et revoir le semi-groupe $a\N + b\N$ que j'aime bien ?). On a donc aidé Zem. Mais peut-être qu'on ne le verra plus car dans son dernier post, il te dit `` Merci. Il est donc a priori difficile d'obtenir une formule simple et utilisable rapidement pour obtenir le nombre de solutions''.
Re: Nombre de triplets solutions de $px+qy+pqz=n$
il y a deux semaines
Exact : j'ai répondu trop vite.

L'idée, dans les deux messages, est de ramener la 3D à la 2D. Mais là s'arrête la ressemblance.
zem
Re: Nombre de triplets solutions de $px+qy+pqz=n$
il y a deux semaines
Bonsoir,
Merci pour votre contribution. Je vais essayer de déchiffrer maintenant smiling smiley
Re: Nombre de triplets solutions de $px+qy+pqz=n$
il y a deux semaines
Zem
Déchiffrer ? Hum, mes posts ne sont PAS self-contained. Est ce que tu souhaites une preuve de la formule $(\heartsuit)$ qui figure dans mon post [www.les-mathematiques.net] ? En cas de réponse positive, je suis susceptible de t'écrire une preuve qui va droit au but, sous forme manuscrite (un scan d'une page).
zem
Re: Nombre de triplets solutions de $px+qy+pqz=n$
il y a deux semaines
Non Claude, déchiffrer est à prendre au sens de comprendre simplement.
Re: Nombre de triplets solutions de $px+qy+pqz=n$
il y a deux semaines
@Zem
Je continue à m'amuser avec tes affaires. J'ai souhaité obtenir une preuve ``directe'' de $v_{n+ab} = v_n + 1$ $(\spadesuit)$ où $v_n$ est le nombre de solutions de $ax + by = v_n$ ou encore $v_n$ est défini par la série :
$$
\sum_{n \ge 0} v_nT^n = {1 \over (1-T^a)(1-T^b)}
$$
Et je me suis aperçu que $(\spadesuit)$ est équivalent à :
$$
\sum_{j \in a\N + b\N} T^j = {1 - T^{ab} \over (1-T^a)(1-T^b)} \qquad\qquad (\blacksquare)
$$
Et là, je suis content car cela rentre dans le terrain de l'Algèbre Commutative ; et je reconnais des séries d'Hilbert-Poincaré. A gauche de $(\blacksquare)$, c'est la série d'Hilbert-Poincaré de l'algèbre de semi-groupe :
$$
\Q[a\N + b\N] \quad \buildrel {\rm def} \over =\quad \Q[T^j, j \in a\N + b\N]
$$
Or on dispose d'un morphisme de $\Q$-algèbres :
$$
\Q[Y, Z] \to \Q[T] , \qquad Y \mapsto T^a, \qquad Z \mapsto T^b
$$
de noyau l'idéal $\langle Y^b - Z^a\rangle $ (il faut penser, en posant $Y = T^a$ et $Z = T^b$, au fait que $Y^b = Z^a$), d'image l'algèbre du semi-groupe. Bilan :
$$
\Q[a\N + b\N] \simeq {\Q[Y,Z] \over \langle Y^b - Z^a\rangle}
$$
Et ce dernier isomorphisme est gradué si l'on donne à $Y$ le poids $a$ et à $Z$ le poids $b$. Et avec un peu de métier, la série d'Hilbert-Poincaré de ${\Q[Y,Z] \over \langle Y^b - Z^a\rangle}$, c'est le membre droit de $(\blacksquare)$.

Bilan : $(\blacksquare)$ est établi donc $(\spadesuit)$ également. Dont on déduit aisément $\fbox {$v_{n+kab} = v_n + k$}$. Et ce dernier encadré, c'est du bon-bon pour la suite $u_n$ qui compte le nombre de solutions de $ax + by + abz = n$.

Cela m'a fait super plaisir de revisiter $a\N + b\N$.
Re: Nombre de triplets solutions de $px+qy+pqz=n$
il y a deux semaines
Bonjour
On peut obtenir de manière assez simple et avec mes notations habituelles la formule suivante donnant le nombre de solutions recherché : $$
\Big(\dfrac{n-p(np^{-1})_q-q(nq^{-1})_p}{pq}\Big)^2+\dfrac{3}{2}\dfrac{n-p(np^{-1})_q-q(nq^{-1})_p}{pq}+1
$$ Al-Kashi



Edité 1 fois. La dernière correction date de il y a deux semaines et a été effectuée par AD.
Seuls les utilisateurs enregistrés peuvent poster des messages dans ce forum.

Cliquer ici pour vous connecter

Liste des forums - Statistiques du forum

Total
Discussions: 124 488, Messages: 1 188 917, Utilisateurs: 19 615.
Notre dernier utilisateur inscrit Gauss716.


Ce forum
Discussions: 4 394, Messages: 52 542.

 

 
©Emmanuel Vieillard Baron 01-01-2001
Adresse Mail:

Inscription
Désinscription

Actuellement 16057 abonnés
Qu'est-ce que c'est ?
Taper le mot à rechercher

Mode d'emploi
En vrac

Faites connaître Les-Mathematiques.net à un ami
Curiosités
Participer
Latex et autres....
Collaborateurs
Forum

Nous contacter

Le vote Linux

WWW IMS
Cut the knot
Mac Tutor History...
Number, constant,...
Plouffe's inverter
The Prime page