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
201 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 solutions de $ax+by+cz=n$

Envoyé par Al-Kashi 
Nombre de solutions de $ax+by+cz=n$
il y a deux semaines
Bonjour,

Je profite de l'exercice proposé par zem [www.les-mathematiques.net] pour relancer le débat.

Après avoir proposé une démonstration élémentaire du théorème de Popoviciu (une variante des résultats obtenus par Tripathi) il y a 8 mois, et d'ailleurs je trouve dommage de ne pas avoir eu de réponse de la part des éditeurs, mais il me semble hélas qu'il est compliqué pour des amateurs de proposer des démonstrations nouvelles et courtes.

À ma connaissance, le nombre de solutions de l'équation $ax+by+cz=n$ n'admet actuellement aucune formule close.
Dans le cas général, j'ai réussi à obtenir un encadrement du nombre de triplets solutions ne dépendant pas de $n$ mais uniquement des deux valeurs minimales $a,b$ et $c$. Supposons que ce soit $a$ et $b$.

On obtient alors un encadrement du type : $$f(a;b;c;n)>D_{3}(n)> f(a;b;c;n)+g(a;b)
$$ Un tel résultat est-il nouveau ? intéressant ?
Al-Kashi



Edité 1 fois. La dernière correction date de il y a deux semaines et a été effectuée par AD.
Re: $ax+by+cz=n$
il y a deux semaines
Qui ne dépend pas de $n$ ? Comment est-ce possible ?

Il existe déjà des encadrements pour ces dénumérants. Par exemple, pour une majoration simple, on a
$$D_k(n) \leqslant \frac{(n+s_k)^{k-1}}{(k-1)!r_k}$$
avec $k \in \mathbb{Z}_{\geqslant 2}$ et où l'on a noté $D_k(n)$ le nombre de solutions dans $\left( \mathbb{Z}_{\geqslant 0} \right)^k$ de l'équation $a_1 x_1 + \dotsb + a_k x_k = n$, les coefficients $\left( a_i \right)$ étant premiers entre eux deux à deux, et $s_k := a_2 + \frac{1}{2} \left( a_3 + \dotsb + a_k \right)$ et $r_k := a_2 \dotsb a_k$.

Ce résultat est conforme avec la formule asymptotique bien connue
$$D_k(n) = \frac{n^{k-1}}{(k-1)! a_1 \dotsb a_k} + O \left( n^{k-2} \right)$$
obtenue en exploitant les propriétés analytiques de la série génératrice de $D_k(n)$ rappelée dans l'autre fil.



Edité 1 fois. La dernière correction date de il y a deux semaines et a été effectuée par noix de totos.
Re: Nombre de solutions de $ax+by+cz=n$
il y a deux semaines
Bonsoir noix de totos,

Je me suis mal exprimé.
Ce que je voulais dire c'était que le terme d'erreur à savoir la fonction $g$ ne dépend pas de $n$.
Re: Nombre de solutions de $ax+by+cz=n$
il y a deux semaines
Bonsoir,

Pour être plus concret :
Si on considère par exemple $5x+11y+47z=n$ je peux donner une formule pour le nombre de solutions avec une erreur de l'ordre de 12 au maximum quel que soit $n$

Al-Kashi
Re: Nombre de solutions de $ax+by+cz=n$
il y a deux semaines
Si ce résultat est juste, il donne un meilleur terme d'erreur, dans le cas $k=3$, que la formule asymptotique écrite plus haut qui, elle, ne fournit pas mieux qu'un reste en $O(n)$.
Re: Nombre de solutions de $ax+by+cz=n$
il y a deux semaines
Bonjour,

Dans ce cas penses-tu qu'un tel résultat a un intérêt ?
Il faut écrire pas mal de lignes au propre, donc je préfère savoir avant d'écrire des formules sans intérêt smiling smiley

Al-Kashi
Re: Nombre de solutions de $ax+by+cz=n$
il y a deux semaines
Je ne suis peut-être pas le mieux placé pour répondre, car les équations diophantiennes ne sont pas mon domaine habituel de travail.

Disons qu'il est usuel de dire que tout ce qui améliore un terme d'erreur antérieur peut avoir son intérêt.

Il faudrait que tu contactes des gens spécialisés dans ce domaine.
Re: Nombre de solutions de $ax+by+cz=n$
il y a treize jours
Al-Kashi
Il y a quelque chose qui m'échappe. Car en dimension 3, 4 (et peut-être même au delà), on dispose du ``polynomial part'' (je ne sais pas comment on dit en français). Par exemple, pour ton problème, le polynôme de degré 2 (en $n$), rationnel en $a,b,c$, suivant :
$$
P_{a,b,c}(n) = {n^2 \over 2abc} + {n \over 2} \left( {1 \over ab} + {1 \over bc} + {1 \over ca} \right) +
{1 \over 12} \left( {3 \over a} + {3 \over b} + {3 \over c} + {a \over bc} + {b \over ca} + {c \over ab} \right)
$$
Et si je note $u_n$ le nombre (exact !) de solutions de $ax + by + cz = n$, on a $u_n = P_{a,b,c}(n) + \text {correctif}$. Et ce correctif est une fonction $abc$-périodique de $n$, donc bornée en $n$. Même mieux, ce correctif est la somme de 3 fonctions (sommes de Fourier-Dedekind), la première étant $a$-périodique, la seconde $b$-périodique, et la troisième $c$-périodique. Ce qui est mieux qu'un quasi-polynôme de longueur $abc$ du point de vue efficacité.

Quand je dis que cela m'échappe, je veux dire plutôt comment est ce que tu te situes par rapport à cette expression ``polynomial part $+$ Fourier-Dekekind-sums'' ? Il me semble que donner un exemple numérique n'est pas non plus convaincant.

Rappel : je ne suis pas du métier (mais j'ai acquis quelques bases de ``convexité algorithmique'' et de géométrie combinatoire) et donc je comprends peut-être de travers.

A une époque, le chapitre I (The Coin-Exchange Problem of Frobenius) de l'ouvrage ``Computing the Continuous Discretly. Integer-point Enumeration in Polyhedra'' de Beck & Robins (Springer, 2007) était accessible sur le net. Mais j'enfonce probablement des portes ouvertes et tu connais tout cela. Ce qui voudrait alors dire qu'il faut mieux spécifier tes petites affaires (disons une meilleure description qualitative car je pense que tu ne souhaites pas montrer tes formules, que tu veux garder secrètes).

Bon courage à toi.
Re: Nombre de solutions de $ax+by+cz=n$
il y a treize jours
Bonjour Claude,

Pour résumé et reprendre tes notations j'ai réussi à simplifier le correctif dont tu parles de sorte que:

$correctif= t_{a,b,c}(n)+correctif'$ où mon $correctif'$ est bornée par les paramètres $a,b$ et $c$
Bien évidemment la fonction $t_{a,b,c}(n)$ est une formule close faisant intervenir les inverses modulaires de $a$ et $b$ par exemple et des restes de parties entières.

Al-Kashi



Edité 1 fois. La dernière correction date de il y a treize jours et a été effectuée par Al-Kashi.
Re: Nombre de solutions de $ax+by+cz=n$
il y a treize jours
Résumons.

Actuellement, on dispose [1] de l'encadrement explicite suivant concernant le dénumérant $D_k(n)$, i.e. le nombre de solutions dans $\mathbb{N}^k$ de l'équation $a_1 x_1 + \dotsb + a_k x_k = n$ avec $i \neq j \Longrightarrow (a_i,a_j) = 1$ :
$$\frac{n^{k-1}}{(k-1)! r_k} \leqslant D_k(n) \leqslant \frac{\left(n + s_k \right)^{k-1}}{(k-1)! r_k}$$
avec $k \geqslant 2$, $s_2 = a_2$, $s_k = a_2 + \frac{1}{2} \left( a_3 + \dotsb + a_k \right)$ ($k \geqslant 3$) et $r_k = a_1 \dotsb a_k$.

Ici, en reprenant tes notations, ça donne, en supposant $a,b,c$ premiers entre eux deux à deux :
$$\frac{n^2}{2 abc} \leqslant D_3(n) \leqslant \frac{\left( n + b + \frac{1}{2} c \right)^2}{2abc}.$$
Fais-tu mieux que ça ?

Référence.

[1] G. Blom & C-E. Fröberg, On money changing, Nordisk. Mat. Tidskr. 10 (1962), 55-69.



Edité 1 fois. La dernière correction date de il y a treize jours et a été effectuée par noix de totos.
Re: Nombre de solutions de $ax+by+cz=n$
il y a treize jours
Bonjour,

Oui noix de totos. Comme je l'ai expliqué dans le premier message j'ai réussi à trouver un encadrement du type:

$f_{a,b,c}(n)<D_{3}(n)<f_{a,b,c}(n)+ k$ où $k$ est une constante.
Si on suppose $a<b<c$ $k$ est de l'ordre de $\dfrac{ab}{2}$

Al-Kashi
Re: Nombre de solutions de $ax+by+cz=n$
il y a treize jours
Alors tu pourrais peut-être présenter ce travail à des spécialistes du domaine, comme M. Beck, S. Robins, R. Diaz, I. Gessel, T. Komatsu ou A. Tripathi par exemple.
Re: Nombre de solutions de $ax+by+cz=n$
il y a treize jours
Al-Kashi
C'est indiscret de te demander ce qu'est $f_{a,b,c}(n)$ dans ton post [www.les-mathematiques.net] ? Comment se fait-il que l'inégalité était dans l'autre sens dans ton premier post ? Une coquille ?
Merci.
Re: Nombre de solutions de $ax+by+cz=n$
il y a treize jours
Comme j'écrivais un nouveau message pour répondre à noix de totos je n'avais pas fait attention au sens dans mon premier message.
Celui-ci n'a pas d'importance tant qu'on a pas précisé la fonction $f$ et qu'on a pas précisé la valeur de $k$

Bon je vais juste déjà vous présenter la fonction dont je parle sur une page. Je proposerai ensuite une preuve si personne ne remet en question cette formule.

Al-Kashi
Re: Nombre de solutions de $ax+by+cz=n$
il y a treize jours
Al-Kashi,
Pour info, cf les références ci-dessous. Je considère le polynôme déjà fourni ce matin
$$
P_{a,b,c}(n) = {n^2 \over 2abc} + {n \over 2} \left( {1 \over ab} + {1 \over bc} + {1 \over ca} \right) +
{1 \over 12} \left( {3 \over a} + {3 \over b} + {3 \over c} + {a \over bc} + {b \over ca} + {c \over ab} \right)
$$
Et je définis la ``sawtooth function''
$$
((x)) = x - \lfloor x \rfloor -1/2
$$
Tu vois que c'est une toute petite fonction ! Et on définit pour $a,b,c \in \N^*$ premiers deux à deux, en notant $a^{-1}$ un inverse de $a$ modulo $c$ :
$$
e_{a,b;c}(n) = \sum_{m=0}^{c-1} \left(\kern -4pt\left( {-a^{-1} (bm -n) \over c} \right)\kern -4pt\right) \left(\kern -4pt\left( {m \over c} \right)\kern -4pt\right)
-{1 \over 4c}
$$
C'est symétrique en $a,b$ et $c$-périodique.

Alors le nombre $u_n$ de solutions de $ax + by + cz = n$ est :
$$
u_n = P_{a,b,c}(n) + e_{a,b;c}(n) + e_{c,a;b}(n) + e_{b,c;a}(n)
$$
Avec des encadrements. Ceci figure dans [arxiv.org] (2003) et version publiée en 2002 [ac.els-cdn.com]


MAIS attention au pata-caisse $t$ versus $-t$ dans ces deux articles concernant l'indexation des sommes de Fourier-Dedekind. Pour comprendre, il faut disposer de leur livre (Beck, Robins) qui date de 2006-2007 et l'avoir sous les yeux.
Re: Nombre de solutions de $ax+by+cz=n$
il y a treize jours
@Claude : je dirais plutôt, si ma mémoire est bonne, que
$$((x)) := \begin{cases} x - \lfloor x \rfloor - \frac{1}{2}, & \textrm{si } x \not \in \mathbb{Z} ; \\ 0, & \textrm{sinon}. \end{cases}$$
Re: Nombre de solutions de $ax+by+cz=n$
il y a douze jours
@noix de totos
Oui, tu as raison. Et ceci constitue un autre pata-caisse. Je m'explique : il y a la fonction sawtooth STANDARD que tu donnes (Apostol y consacre un chapitre entier), cf les travaux de Rademacher, Grosswald ... Celle que j'évoque, avec la même notation i.e. celle de l'article de Beck, Diaz & Robins, est ``differing slightly'' i.e. vaut $-1/2$ sur $\Z$ et pas $0$. Ces auteurs ont trouvé le moyen d'avoir la même notation pour deux fonctions différentes, dans leur article et dans leur livre (cf chapitres 7 et 8).! Ce n'est pas de ma faute.

A propos de ce que j'appelle le patacaisse $t$ versus $-t$ dans mon post précédent. Dans l'article, $\mathbb N$ désigne $\mathbb Z_{\ge 1}$ et pas $\mathbb Z_{\ge 0}$. Leur fonction de dénombrement pour $A = (a_1, \cdots, a_d)$ associée est notée $p'_A(n)$ i.e. elle compte le nombre de $d$-uplets entiers strictement positifs $(x_1, \cdots, x_d)$ vérifiant $a_1x_1 + \cdots + a_dx_d = n$. Et se nomme dans l'article ``restricted partition function of $A$''. A ne pas confondre avec $p_A(n)$ où strictement positif est remplacé par positif ou nul. Sauf que $p_A$ porte aussi le nom, dans le livre, de ``restricted partition function''.

Et dans le livre, $p'_A$ est notée $p^\circ_A$. Dans l'article, c'est $p'_A$ qui intervient presque uniquement. Tandis que dans le livre, c'est $p_A$. Mais $p'_A$ et $p_A$, même combat grâce à la loi de réciprocité :
$$
p'_A(-n) = (-1)^d p_A(n)
$$
Attention du coup au polynôme ``partie principale'' pour lequel il faut alterner les coefficients lorsque l'on passe de la partie principale relativement à $p_A$ à la partie principale relativement à $p'_A$. Je ne sais pas si c'est bien clair mais ce n'est pas que de ma faute. Je veux dire qu'il faut faire très attention entre le livre et l'article. De mon côté, je ne peux pas faire autrement que de faire attention car je bosse avec des programmes ``numériquement certifiés''.

Par ailleurs, j"avais bien raison : quelque soit la dimension $d$, le polynôme partie principale (de degré $d-1$) a été explicité dans le cas général depuis 2001 (Beck, Gessel, Komatsu), cf les références bibliographiques de Beck, Diaz & Robin (il s'agit de la référence [3]).

Enfin, il y a une erreur dans l'article, page 16 au milieu. On a la majoration (pour la notation, cf mon post précédent)
$$
|e_{a,b ; c}| \le {1\over 12} (c + 5/c) \qquad \hbox {et pas} \qquad |e_{a,b ; c}| \le {1\over 12} (c + 1/c)
$$
Attention : la notation $e$, c'est perso : chez les 3 auteurs, c'est $\sigma$. Mais je n'ai pas voulu l'utiliser à cause du patacaisse $t$ versus $-t$.

J'ai l'impression que ce post est obscur. Si c'est le cas, prendre l'article, le livre. Et lire.
Re: Nombre de solutions de $ax+by+cz=n$
il y a douze jours
Hello,

Mon post précédent donne l'impression que je suis critique en ce qui concerne les auteurs. Je corrige donc le tir (après tout, on n'est pas obligé d'avoir des notations analogues entre un article et un livre).

L'ouvrage de Beck & Robbins, Computing the Continuous Discretely (Integer-Point Enumeration in Polyhedra), [www.springer.com] est un très beau livre, très pédagogique, avec une progression bien contrôlée, beaucoup d'exemples ...etc... Pourquoi ne pas se faire un petit cadeau pour Noël ?

Et dans l'article, on voit l'efficacité de deux méthodes (section 2 The Residue Method, section 3 The Fourier Method) qui conduisent aux mêmes résultats. Et cela met un peu de bonne humeur dans le monde de la somme de Dedekind (section 3 : The Fourier-Dedekind sum), monde qui paraît de premier abord relativement technique. Je crois comprendre que ``Part of This work appeared in the first author's Ph.D Thesis''. I.e. Matthias Beck.

Et des liens apparaissent avec le monde modulaire via les Dedekind $\eta$-products, cf l'article de S. Robins. De quoi ne pas s'ennuyer en 2018.
Re: Nombre de solutions de $ax+by+cz=n$
il y a onze jours
Histoire de terminer quelque chose, je réponds à l'initiateur du fil concernant sa question de formule close pour le nombre de solutions de $ax + by + cz = n$, lorsque $a,b,c$ sont premiers deux à deux. Pour moi, la réponse est oui et figure dans les écrits de Beck & Robins (articles et livre, j'ai donné des références). J'ai essayé de rapporter cette formule close dans les posts ci-dessus. Et l'implémentation est d'une simplicité enfantine comme le montre le peu de lignes du code ci-dessous. Note : &+[...] est la somme de la séquence.

// Attention à Round, Floor, Truncate, Ceiling.
// sawtooth fonction NON standard (sur Z -1/2 au lieu de 0) Page 13 de l'article.
// Fonction sawtooth standard : Apostol, p. 61 (chap. 3), Livre de Beck/Robins, chap. 7
SawtoothFunction := func < x | x - Floor(x) - 1/2 > ;

PeriodicTerm := function(a,b, c)
  a_inv_mod_c := Modinv(a,c) ;
  // Attention au patacaisse -n versus n
  term := func < m, n | SawtoothFunction(-a_inv_mod_c * (b*m - n)/c) * SawtoothFunction(m/c) > ;
  return map < N -> Q | n :-> &+[Q| term(m,n) : m in [0..c-1]] - 1/(4*c) > ;
end function ;

PolynomialPart := function(abc)
  a,b,c := Explode(abc) ;
  ab := a*b ;  bc := b*c ;  ca := c*a ;
  return X^2/(2*a*b*c)  +  X/2*(1/ab + 1/bc + 1/ca)  +  1/12*(3/a + 3/b + 3/c + a/bc + b/ca + c/ab) ;
end function ;

BeckRobins := function(abc)
  a,b,c := Explode(abc) ;
  assert Gcd(a,b) eq 1 and Gcd(a,c) eq 1 and Gcd(b,c) eq 1 ;
  e_ab_c := PeriodicTerm(a,b, c) ;
  e_ca_b := PeriodicTerm(c,a, b) ;
  e_bc_a := PeriodicTerm(b,c, a) ;
  P := PolynomialPart(abc) ;
  return map < N -> N | n :-> Evaluate(P,n) + e_ab_c(n) + e_ca_b(n) + e_bc_a(n) > ;
end function ;

Efficacité ? Lire le chapitre 7 du livre de Beck & Robins. Je suis loin d'en avoir fait le tour mais on voit qu'un certain nombre de résultats de réciprocité (dans le désordre : Don Zagier, Dedekind, Rademacher) peuvent constituer des accélérateurs dans le calcul des sommes (de longueur fixe $a, b, c$) qui interviennent.

Quant à la petite erreur dans l'article dont j'ai parlé dans un post, j'ai contacté les auteurs. L'un d'ente eux m'a répondu. Visiblement, cela n'impacte pas sur le théorème 9 p. 17 (majoration du nombre de Frobenius d'un semi-groupe de $\N$, nombre de Frobenius = plus grand entier NON dans le semi-groupe).

Je ne sais pas si dans ce fil nous verrons de nouveau son initiateur. J'estime avoir répondu de manière précise et constante à ses interrogations.
Re: Nombre de solutions de $ax+by+cz=n$
il y a onze jours
À propos de Matthias Beck : je lui avais, apparemment, fourni une référence (sans doute Popoviciu ou du même genre), mais je l'avais complètement oublié. Aussi, quelle ne fut pas ma surprise de me voir dans ses remerciements de l'un de ses articles, plusieurs années plus tard, alors que ma contribution ne le méritait sans doute pas.

Très sympa, ce Beck.
Re: Nombre de solutions de $ax+by+cz=n$
il y a onze jours
@noix de totos
C'est lui qui m'a répondu.

Chaque chapitre du livre de Beck et Robins est suivi de notes. Je vois que Popoviciu, cela date de 1953, et si je comprends bien ce que disent les auteurs, c'est que ce résultat a été redécouvert à plusieurs reprises (1989, 1998).

A propos d'Ehrhart : il y est mentionné (fin du chapitre 3) qu'une grande partie de son travail, il l'a réalisé quand il était au lycée (en italique) de Strasbourg. Et qu'il a passé un doctorat à 60, ans, poussé par ses collègues.
Re: Nombre de solutions de $ax+by+cz=n$
il y a onze jours
Bonjour Claude,

Merci pour ta contribution.

Néanmoins, lorsque je parle d'une formule close, il s'agit de faire disparaitre toutes les sommes.
Je ne te rejoins donc pas sur ce point.

Il doit être très complexe d'en obtenir une.

La différence avec le résultat que j'obtiens est celle mentionnée dans mon premier message, c'est à dire la possibilité d'avoir un encadrement avec un terme d'erreur constant.

Sauf erreur de ma part, un tel résultat n'existe pas.

Ensuite en terme de rapidité de calcul, dans ma relation, le terme d'erreur correspondant à deux sommes majorées en $a$ et $b$ , je pense que celle-ci sera plus rapide. Attention je suis une bille en programmation, donc à confirmer plus tard par les spécialistes.

Al-Kashi

J'aborderai aussi du coup le problème de Frobénius dans notre cas. Néanmoins je ne connais pas les meilleurs résultats à ce sujet obtenus dans le cas $k=3$
Re: Nombre de solutions de $ax+by+cz=n$
il y a onze jours
Al-Kashi,
Le polynôme $P_{a,b,c}$ vérifie $$
| u_n - P_{a,b,c}(n)| \le {1 \over 12} (a+b+c + 5/a + 5/b + 5/c)
$$



Edité 1 fois. La derni&egrave;re correction date de il y a onze jours et a &eacute;t&eacute; effectu&eacute;e par AD.
Re: Nombre de solutions de $ax+by+cz=n$
il y a onze jours
En effet tu as raison.
Le type d'encadrement que je voulais proposer existe donc déjà.

Bon je pense que ma formule n'a plus que très peu d'intérêt à part un petit gain de temps dans les calculs.

Je vais quand même vous la présenter du coup.

Merci Claude.

Al-Kashi
Re: Nombre de solutions de $ax+by+cz=n$
il y a dix jours
@Claude Quitté : oui, Popoviciu [2] date de 1953, et, depuis, il y a eu diverses variantes de cette identité. En voilà une due à Tripathi [3] (voir aussi [1, Chapter 2]) :

Si $(a,b)=1$ et si $\left( a^\star, b^\star \right) \in \left[ 0,b \right] \times \left[ 0,a \right]$ sont les entiers vérifiant $aa^\star + n \equiv 0 \pmod b$, $bb^\star + n \equiv 0 \pmod a$, alors le nombre $D_2(n)$ de solutions dans $\mathbb{N}^2$ de solutions de l'équation $ax+by=n$ est égal à
$$D_2(n) = \frac{n}{ab} - 1 + \frac{a^\star}{b} + \frac{b^\star}{a}.$$

Références.

[1] O. Bordellès, Arithmetic Tales, UTX, Springer, 2012.

[2] T. Popoviciu, Asupra unei probleme de patitie a numerelor, Stud. Cercet Stiint - Acad. RP. Rom,. Fil. Cluj. 4 (1953), 7--58.

[3] A. Tripathi, The number of solutions to $ax+by=n$, Fibonacci Q. 38 (2000), 290--293.



Edité 3 fois. La derni&egrave;re correction date de il y a dix jours et a &eacute;t&eacute; effectu&eacute;e par noix de totos.
Re: Nombre de solutions de $ax+by+cz=n$
il y a dix jours
@noix de totos
Merci pour les références. Mais je ne suis que de passage dans ce fil comme tu sais. Du coup, peut-être ce Dimanche, on peut en profiter pour parler des petites imperfections de notre bas monde.

Je vois ainsi, dans l'index de l'ouvrage de Bordellès, qu'à Popoviciu, il y a seulement un pointeur sur la page 544. Et que l'on eût préféré un pointeur sur l'exercice 12 du chapitre 2, page 54. Exercice corrigé s'il vous plaît. Pas grave car en fait, la page 544 pointe sur cet exercice.

Et on eût aimé (décidément) que parfois (pas toujours) la notation $D_{(a,b)}(n)$ soit utilisée au lieu de $D_2(n)$. Idem pour la notation $D_3(n)$. Voir, à la page 50 de l'ouvrage, la formule close pour $D_{(1,2,3)}(n)$ aurait été du plus grand effet.

Idem, dans le résultat que tu cites, on peut s'interroger sur la notation $a^\star$ qui varie avec $n$. Pourquoi ne pas mentionner un indice $n$ quelque part ? Trop lourd peut-être ? Je dis cela en pensant au théorème de Popoviciu où intervient la notation $a^{-1}$ indépendante de $n$ (elle désigne un inverse modulo de $a$ modulo $b$).

Vraiment trois fois rien comme tu vois.

Et aussi pour te signaler que de fil en aiguille, de pointeurs sur le Net en autres pointeurs ...etc.. j'ai fini par mettre la main (certes, ce n'était pas difficile) sur un certain papier de Beck & Robins contenant une certaine note de bas de page. Confirmant ce que j'avais deviné depuis fort longtemps.
Re: Nombre de solutions de $ax+by+cz=n$
il y a dix jours
A priori, il utilise parfois la notation $D_{(a,b,c,\dotsc)}(n)$ pour des dénumérants lorsque les coefficients ont besoin d'être spécifiés (voir par exemple Proposition 7.118) mais, sinon, je n'ai rien contre les notations $D_2(n)$, $D_3(n)$ (je les ai moi-même employées ci-dessus), du moment qu'il n'y ait pas de risque de confusion, et que tout le monde comprend de quoi il s'agit.

De même pour la notation $a^\star$. Certes, il dépend de $n$ mais le contexte est clair, et ça ne me semble pas nécessaire de le préciser.

D'une manière générale, je ne suis pas trop pour alourdir des notations si le contexte est clair, car ça contribue à une lecture lourde et pénible qui ne rend pas l'ensemble très agréable à aborder. J'ai eu récemment à arbitrer un article pour une revue, et les notations très lourdes ont failli me faire rejeter ce manuscrit. Il a finalement été accepté au prix d'un sérieux "nettoyage" de la part de son auteur.



Edité 1 fois. La derni&egrave;re correction date de il y a dix jours et a &eacute;t&eacute; effectu&eacute;e par noix de totos.
Re: Nombre de solutions de $ax+by+cz=n$
il y a sept jours
avatar
noix de totos écrivait : [www.les-mathematiques.net]
-------------------------------------------------------
> Ici, en reprenant tes notations, ça donne, en supposant $a,b,c$ premiers entre eux deux à deux : $$ \frac{n^2}{2 abc} \leqslant D_3(n) \leqslant \frac{\left( n + b + \frac{1}{2} c \right)^2}{2abc}.$$
Pour l'équation $5x + 13y + 21z = 5$ par exemple, il y a 1 solution, or le terme de droite de l'encadrement est inférieur à 1 (0,297..). Où est-ce que ça cloche ?



Edité 1 fois. La derni&egrave;re correction date de il y a sept jours et a &eacute;t&eacute; effectu&eacute;e par AD.
Re: Nombre de solutions de $ax+by+cz=n$
il y a sept jours
Le terme $a$ au dénominateur du membre de droite est en trop.
Re: Nombre de solutions de $ax+by+cz=n$
il y a sept jours
avatar
Ah ok.
Merci.
Re: Nombre de solutions de $ax+by+cz=n$
il y a six jours
avatar
Salut @noix de totos.
Une remarque sur le membre de gauche aussi. Par exemple l'équation$5x + 13y + 21z = 7$ n'a pas de triplet solution et ce membre est supérieur à $0$ ?
Re: Nombre de solutions de $ax+by+cz=n$
il y a six jours
@babsgueye et noix de totos
On voit maintenant qu'il y a une erreur dans la minoration $D_{a,b,c}(n) \ge n^2/(2abc)$ fournie par noix de totos dans [www.les-mathematiques.net]. Une telle minoration fournirait $D_{a,b,c}(n) > 0$ pour $n \ge 1$, conduisant au fait que $a\N + b\N + c\N = \N$.

Déjà dit : une minoration est fournie en bas de la page 16 de [arxiv.org]. Mais attention à deux choses : premièrement, le polynôme qui intervient en première partie de l'inégalité est le polynôme partie principale de $p'_{(a,b,c)}$ (avec les notations de Beck, Diaz, Robins) et non de $p_{(a,b,c)}$ i.e. pata-caisse $t$ versus $-t$ déjà évoqué. Et deuxièmement, la minoration sur $\sigma_t(a,b;c)$ (ici, encore je prends les notations des auteurs) est erronée : $1/(12c)$ doit être remplacé par $5/(12c)$. Et donc également, celles sur $\sigma_t(c,a;b)$ et $\sigma_t(b,c ;a)$.

Bref, la minoration qui figure à l'avant dernière ligne de la page 16 de l'article doit être corrigée. Je parle du facteur qui figure devant le terme $1/a + 1/b + 1/c$.
Re: Nombre de solutions de $ax+by+cz=n$
il y a six jours
En effet, l'article de Blom & Fröberg est hautement suspect.

Décidément, il faut faire tout soi-même...smoking smiley

Une mention spéciale à l'œil vif de babsgueye.

Quant à celle de Beck et Al, je connaissais ce preprint, mais je voulais un encadrement plus en rapport avec l'égalité asymptotique de ces dénumérants.

La majoration
$$D_k (n) \leqslant \frac{(n+s_k)^{k-1}}{(k-1)! r_k} \quad \left( k \geqslant 1 \right)$$
où $s_1 = 0$, $s_2=a_2$, $s_k = a_2 + \frac{1}{2} \left( a_3 + \dotsb + a_k \right)$ si $k \geqslant 3$, et $r_1=1$, $r_k = a_2 \dotsb a_k$ si $k \geqslant 2$, me semble correcte.

À noter : dans un preprint sorti hier [arxiv.org], l'auteur propose l'encadrement suivant, toujours avec $a,b,c$ premiers entre eux deux à deux :

$$\left | D_3(n) - \frac{abc}{2} \left \lfloor \frac{n}{abc} \right \rfloor^2 \right | \leqslant n \left( 1 + \frac{c-ab+1}{2abc} \right) + \tfrac{1}{2} \left( ab(c+3)+c+1 \right).$$
Re: Nombre de solutions de $ax+by+cz=n$
il y a six jours
Bonjour,

Ma formule étant un peu barbare, je vous explique juste l'origine de celle-ci.
Il s'avère que pour trouver une formule exacte pour $D_{(a,b,c)}$ j'ai réussi à me ramener à un problème du type $D_{(1,p,q)}$
Or il y a quelques années j'avais réussi à donner un encadrement de ce dénumérant ( voir fichier joint) dépendant de $p$.

Ceci revient à dire que pour trouver une formule exacte, il suffit de savoir compter de manière exacte le nombre de points entiers sous une droite. J'avais pas mal étudié le terme d'erreur mais celui-ci est très complexe à maitriser.

Ps: On peut alléger les calculs dans le fichier mais je ne l'ai pas fait depuis en raison du manque de temps.

Al-Kashi
Pièces jointes:
ouvrir | télécharger - AliouiAbdelhak_A_propos_des_dénumérants.pdf (121.7 KB)
Re: Nombre de solutions de $ax+by+cz=n$
il y a deux heures
Bonsoir,

Les seuls cas où j'ai réussi à obtenir des formules clairement closes sont les suivants:
Supposons $a$ et $b$ premiers entre eux.
Soit $k$ un entier. Les dénumérants de types:

$D_{(a,b,kab)}$ , $D_{(a,b,a+b+kab)}$, $D_{(a,b,a-b+kab)}$ , $D_{(a,b,-a-b+kab)}$ et $D_{(a,b,b-a+kab)}$

admettent des formules closes.

Par exemple, si on choisit $a=11$ et $b=7$ on obtient des formules closes pour

$D_{(7,11,77k)}$, $D_{(7,11,18+77k)}$, $D_{(7,11,-4+77k)}$, $D_{(7,11,-18+77k)}$ et $D_{(7,11,4+77k)}$

Al-Kashi
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 422, Messages: 1 188 126, Utilisateurs: 19 587.
Notre dernier utilisateur inscrit Grg57.


Ce forum
Discussions: 4 389, Messages: 52 470.

 

 
©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