Nombre de triplets solutions de $px+qy+pqz=n$
dans Arithmétique
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.
Bonjour
Auriez-vous des idées pour aborder le problème ci-dessus dans $\mathbb N$ avec $p$ et $q$ premier entre eux.
Merci.
Connectez-vous ou Inscrivez-vous pour répondre.
Réponses
$$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).$$
Pensez vous qu'une formule exacte serait envisageable ?
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)$$
où
$$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.
Il est donc a priori difficile d'obtenir une formule simple et utilisable rapidement pour obtenir le nombre de solutions.
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.
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}
$$
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.
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
http://www.les-mathematiques.net/phorum/read.php?5,1570026,1571078#msg-1571078 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 http://www.les-mathematiques.net/phorum/read.php?5,1570026,1570896#msg-1570896 (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''.
L'idée, dans les deux messages, est de ramener la 3D à la 2D. Mais là s'arrête la ressemblance.
Merci pour votre contribution. Je vais essayer de déchiffrer maintenant :-)
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 http://www.les-mathematiques.net/phorum/read.php?5,1570026,1571368#msg-1571368 ? 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).
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$.
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