Base additive d'ordre 2 ?

Bonjour,

Peut-on construire une suite $(u_n)_{n \geqslant 0}$ d'entiers naturels telle que $\lim\limits_{n\rightarrow +\infty}(u_{n+1}-u_n)=+\infty$ et telle que pour tout $N\in\mathbb{N}$, il existe $(n,m)\in\mathbb{N}^2$ tel que $N=u_n+u_m$ ?

Après quelques vérifications informatiques (pas très poussées cependant), il est possible que cela soit vrai pour $u_n=\sum\limits_{k=0}^{n} {\lfloor \sqrt{k} \rfloor}$ ?

Avez-vous des idées ? Des références concernant des questions connexes ? Merci d'avance !

Réponses

  • Bonjour.
    J'ai testé
    $$
    u_0=1 \; , \quad u_n=u_{n-1}+E(\ln n)
    $$
    (E est la partie entière).
    Avec les 5000 premiers termes, les sommes de deux termes donnent tous les entiers jusqu'à $50\,000$.
    Cordialement.
  • Oui, j'avais testé également de telles suites $u$, pour lesquelles la divergence de $u_{n+1}-u_n$ est plus lente.
    Des idées pour une démonstration ?
  • Non, malheureusement.

    Bon courage.
  • Bonjour uvdose,

    peut-on en savoir plus sur l'origine de ce problème ?

    S
  • J'ai découvert le sujet des bases additives très récemment... Il est classique que si $A$ est une partie de $\mathbb{N}^*$ dont la densité de Schnirelmann $\sigma(A)$ est supérieure ou égale à $\frac12$, alors $A\oplus A=\mathbb{N}^*$. J'ai commencé par me demander s'il était possible d'avoir $A\oplus A=\mathbb{N}^*$ avec $\sigma(A)=0$ ; il me semble que la réponse est positive en prenant $A=\left\{\sum\limits_{k\in K}4^k\, , \, \emptyset\neq K\subset \mathbb{N}\right\} \cup \left\{\sum\limits_{k\in K}2\times4^k\, , \, \emptyset\neq K\subset \mathbb{N}\right\}$. De fil en aiguille, j'ai fini par me poser (tout seul comme un grand), la question au début de ce fil... Mais je ne parviens pas à progresser.
  • Puisqu'on est dans le forum "Arithmétique"... :-)

    Tu peux, sauf erreur, considérer la suite des nombres qui sont la somme de deux carrés.

    D'après le théorème de Lagrange, cette suite forme une base additive d'ordre 2.
    Par ailleurs, un théorème de Landau (cf. wikipedia) permet de voir que le $n$-ième terme de cette suite est équivalent à $c n \sqrt{\ln{n}}$, où $c$ est l'inverse de la constante de Landau-Ramanujan qui fait l'objet de l'article de wikipedia.
  • Mais le fait que $u_n\sim cn\sqrt{\ln n}$ n'implique pas forcément que $u_{n+1}-u_n\rightarrow+\infty$. De toute façon, si $u_n$ désigne le $n-$ième entier naturel somme de deux carrés d'entiers naturels, il est clair que $u_{n+1}-u_n$ ne diverge pas vers $+\infty$...
  • En effet, j'ai réalisé ça peu après avoir posté mon message...
    En revanche, on a (sauf nouvelle erreur...) $\limsup (u_{n+1} - u_n) = +\infty$.

    Je crois avoir une construction répondant à ta question, mais je préfère vérifier les détails avant de la poster.
  • Merci de te pencher sur la question analystedudimanche (surtout un samedi !).

    J'avais également réussi à construire une suite $(u_n)$ vérifiant seulement $\limsup (u_{n+1}-u_n)=+\infty$ de la façon suivante :
    $u_0=0$ et pour tout $n\in\mathbb{N}^*$, $u_n$ est le $n-$ième terme de l'ensemble $\bigcup\limits_{k\in\mathbb{N}}[\![2^{2k};2^{2k+1}]\!]$.

    N'hésite pas à poster ta construction !
  • Ma construction est un peu dans le même esprit, en fait.

    Soient $(F_k)$ la suite de Fibonacci et $(G_k)$ la suite définie par $G_0 = 0$ et, pour $k \ge 1$, $G_k = \sum_{j=1}^{k-1} F_j F_{j+3}$ (cette somme peut se calculer explicitement et vaut $F_{k+1}^2-1$, mais ce n'est pas très utile pour la suite).
    On définit ensuite les ensembles $A_k = G_k \oplus F_k \diamond [\![ 0, F_{k+3} ]\! ]$ où, pour un entier $p$ et un ensemble $E$, $p \diamond E = \{ pe \, : \, e \in E \}$ (chaque $A_n$ est donc une suite arithmétique finie).

    Alors je prétends que la suite $(u_n)$ définie par $u_0 = 0$ et, pour $n\ge1$, $u_n$ est le $n$-ième terme de l'ensemble $A = \bigcup_k A_k$, a les propriétés désirées.

    Je posterai la preuve plus tard, si nécessaire.
    Elle part de l'observation suivante : on a $G_1 = 0$, $G_2 = 3$ et $A_1 = [\![0, 3]\!]$, donc $[\![2G_1, 2G_2 ]\!] = [\![0, 6]\!] = A_1 \oplus A_1$. Il n'est pas vrai que cela continue comme ça, mais l'idée est de montrer que l'on peut représenter les entiers des intervalles de la forme $[\![2G_k, 2G_{k+1} ]\!]$ comme somme d'un entier de $A_{k-1}$ et d'un entier soit de $A_k$ soit de $A_{k+1}$, du coup en considérant l'union de tous ces ensembles on a la propriété d'être une base additive d'ordre 2.

    Par ailleurs, en notant, pour $k \ge 1$, les sommes partielles $S_k = \sum_{j=1}^{k-1} F_{j+3}$ (ici encore, on peut avoir une formule explicite mais ce n'est pas utile), un entier $n$ se trouve toujours entre deux termes consécutifs de cette suite, disons $S_k \le n < S_{k+1}$ pour un certain $k$, et par construction de $A$ il n'est pas difficile de voir qu'on a alors $u_n = G_k + (n - S_k)F_k$. On en déduit que $u_{n+1} - u_n = F_k$ et finalement $\lim (u_{n+1}-u_n)=+\infty$.

    J'espère ne pas avoir écrit (trop) de bêtises... :-)
  • Je n'ai pas vérifié tous les détails de ta construction mais elle contient effectivement un ingrédient auquel je n'avais pas pensé (tu).

    Sauf erreur(s), voici ce que je propose en guise de simplification :

    On pose $A_0=\{0\}$ et pour $k\in\mathbb{N}^*$, $A_k=\{ak, 0\leqslant a \leqslant k+5 \}$. En notant $u_n$ le $n-$ième terme de $A=\bigcup\limits_{k\in\mathbb{N}}A_k$ pour $n\in\mathbb{N}^*$, la suite $(u_n)$ répond à la question initiale.

    Éléments de preuve : on peut voir que pour tout $k\in\mathbb{N}$, $[\![k(k+1);(k+1)(k+2)]\!]$ est contenu dans $A_k+A_{k+1}$. En effet c'est clair lorsque $k=0$ ; supposons $k\geqslant1$. Si $k(k+1) \leqslant n \leqslant (k+1)(k+2)$, l'étude de l'équation de Bézout $kx+(k+1)y=n$ montre facilement qu'il existe une solution $(x,y)$ avec $0\leqslant x \leqslant k+5$ et $0\leqslant y\leqslant k+2$ (détails fournis sur demande).

    Le fait que $(u_{n+1}-u_n)$ diverge vers $+\infty$ ne pose pas de problème.

    Encore merci pour ton aide précieuse !
  • Joli, bien vu !
    Content d'avoir pu t'aider.
  • J'ai suivi ce fil avec intérêt et trouve très chouette la première idée d'analystedudimanche.
    Aussi, merci uvdose d'avoir répondu à ma question indiscrète.

    Ceci dit je n'arrive pas à me convaincre de la divergence de $u_{n+1}-u_n$ vers $+\infty$ (dans la version que vous proposez uvdose).

    S
  • Oui, samok, à bien y réfléchir, il me semble que je me suis avancé :-(
    Mon truc est même complètement à côté de la plaque !
  • @analystedudimanche : ton ensemble $A_k$ est bien défini par $\left\{p(F_k+G_k), p\in[\![0;F_{k+3}]\!]\right\}$, de sorte qu'on a les suites arithmétiques finies : $A_1=\{0;1;2;3\}$, $A_2=\{0;4;8;\cdots;20\}$, $A_3=\{0;10;20;\cdots;80\}$, $A_4=\{0;27;54;\cdots;351\}$, $A_5=\{0;68;136;\cdots;1428\}$ etc. ? Mais quelque chose m'échappe car j'ai l'impression que par exemple $25$, $65$ (et d'autres) ne seront pas dans $A\oplus A$ ?
  • Bonjour,

    quelque chose me dérange dans votre version analystedudimanche, c'est aussi relatif à la divergence de $(u_{n+1}-u_n)$.
    J'ai tenté les calculs pour voir si ça se simplifiait comme vous dites, je n'ai pas abouti. Puis je me suis rendu compte qu'implicitement je prenais pour acquis que : si $u_n$ est relatif à un certain nombre $k$, alors $u_{n+1}$ est relatif à $k+1$. Ce qui est faux.

    Qu'en pensez-vous ?

    [small]Par ailleurs, voici ce qu'un petit lutin m'a soufflé à l'oreille quand j'ai pris connaissance du problème : théorème de Zeckendorf ! mais je n'ai pas saisi où voulait en venir ce petit lutin. Peut-être que ça vous inspirera.[/small]

    S
  • Décidément, cette condition $\lim (u_{n+1}-u_n) = +\infty$ fait des ravages :)o

    Je pense toujours que ma construction fait l'affaire, et peut-être que le problème vient du fait que je n'ai pas bien expliqué la définition de mes $A_k$ (j'aurais dû écrire $A_k = \{G_k\} \oplus F_k \diamond [\![0, F_{k+3}]\!]$) :
    $A_k = \{ G_k + pF_k \, : \, p \in [\![0, F_{k+3}]\!] \}$.
    Donc, avec $G_1=0, G_2=3,G_3=8$ (pour le coup la formule explicite pour $G_k$ est utile), $A_1 = \{0, 1, 2, 3\}, A_2 = \{3, 4, 5, 6, 7, 8\}, A_3 = \{8\} \oplus 2 \diamond [\![0, F_6]\!] = \{8, 10, 12, \ldots, 24\}$, etc.
  • Je viens de comprendre le rôle des $G_k$.
    J'ai compris la construction et je suis d'accord que ça marche pour la divergence de $u_{n+1}-u_n$.
    Je regarderai plus tard si bien une base additive d'ordre 2.
    En tout cas je trouve ça très bien ajusté.

    S
  • Ok analystedudimanche, j'ai compris ta construction de $A$ et valide bien sûr le fait que $(u_{n+1}-u_n)$ diverge vers $+\infty$.

    Peux-tu poster quelques détails pour prouver que $[\![2G_k;2G_{k+1}]\!] \subset (A_{k-1}+A_k)\cup(A_{k-1}+A_{k+1})$ ? Ce n'est pas absolument clair pour moi... Je pense que tu dois utiliser le fait que pour tout $k \in \N^*$, on a $F_{k-1}\wedge F_k=F_{k-1}\wedge F_{k+1}=1$ ? D'ailleurs est-ce cela qui t'a fait penser à Fibonacci ?
  • Bon, j'ai regardé et ben je sèche, j'ai contemplé des résultats sur tableur, il y a des choses qui se dégagent mais bon ...
    C'est bien ficelé et je vois pas les noeuds. De la belle ouvrage.

    S
  • Bonjour uvdose,

    je crois que j'ai compris, voici si vous voulez uvdose ce qui me semble déterminant :

    - pour tout entier naturel $k$ :$F_{k+1}.F{k-1}+(-F_k).F_k=1$
    - faire en sorte de trouver des entiers consécutifs de $A_{k-1}+A_k$, touiller bidouiller un peu
    - semblablement pour $A_{k-1}+A_{k+1}$

    Je trouve votre construction superbe analystedudimanche.
    Bravo! et Merci pour ce zouli keutru quand même un peu diabolique non ?

    [small](et ça m'a donné une idée de jeu pour les petites nenfants)[/small]

    S
  • Oui samok, j'avais pensé à quelque chose comme ça. En fait l'identité est $F_{k+1}F_{k-1}-F_k^2=(-1)^k$.
    Mais j'espère qu'il ne faudra pas attendre dimanche prochain pour qu'analystedudimanche nous donne la recette exacte :-)
  • oui effectivement je me suis gourré dans l'identité.
    J'essaierai de mettre tout ça au propre dans la semaine, parce que j'aime beaucoup le problème et la solution proposée.

    S
  • Bonsoir à vous deux,

    Je m'excuse de ne pas avoir pu répondre avant (je suis un peu occupé en ce moment), mais vous avez effectivement compris l'une des clés de la construction (la propriété $F_m \wedge F_n = F_{m \wedge n}$).

    Une autre observation utile est la suivante : par définition des $A_k$, on a $G_k \in A_k$; de plus par définition des $G_k$, on a $G_{k+1} = G_k + F_k F_{k+3}$, et ainsi $G_{k+1} \in A_k$.
    Ceci nous permet de voir $A_k$ comme $\{ G_{k+1} - q F_k \, : \, q \in [\![0, F_{k+3}]\!] \}$.

    Maintenant, étant donné un entier $n \in [\![2G_k, 2G_{k+1}]\!]$, l'idée est de trouver $p$ et $q$ dans les intervalles qu'il faut pour avoir $n = (G_k - pF_{k-1}) + (G_l + qF_l)$ où $l \in \{k, k+1\}$ selon l'endroit où $n$ se trouve dans l'intervalle.

    Pour ce faire on utilise la propriété que vous avez souligné. Par exemple, de $F_{k-1} \wedge F_k = 1$, on obtient l'existence (et l'unicité) d'un $p \in [\![0, F_{k+3}]\!]$ tel que $n \equiv 2G_k - p F_{k-1} \mod F_k$ avec $p \in [\![0, F_{k+2}]\!]$. Ceci nous fournit l'existence et l'unicité d'un $q$ tel que $n - 2G_k + p F_{k-1} = qF_k$ et si on choisit bien le sous-intervalle dans lequel on prend $n$ on peut faire en sorte que ce $q$ soit inférieur ou égal à $F_{k+3}$ et conclure dans ce cas.
    Le cas restant est du même acabit en utilisant cette fois la propriété $F_{k-1} \wedge F_{k+1} = 1$ pour démarrer.
  • [small]bon j'ai rien compris à ce que j'avais compris (le fait d'être premier entre eux était secondaire, l'identité qui les reliait était plus conséquente)[/small]

    S
  • Add a écrit:
    et si on choisit bien le sous-intervalle dans lequel on prend $n$ on peut faire en sorte que ce $q$ soit inférieur ou égal à $F_{k+3}$ et conclure dans ce cas

    J'avoue, analystedudimanche, que je reste un peu sur ma faim... Quelques détails supplémentaires ne seraient pas superflus, en ce qui me concerne.

    Si j'ai bien compris, tu parviens à montrer qu'il existe deux entiers naturels $B_k$ et $C_k$ avec $F_kF_{k+3}\leqslant B_k+C_k$ tels que $\left\{qF_k-pF_{k-1} \, , \, 0\leqslant q \leqslant F_{k+3} \, , \, 0\leqslant p \leqslant F_{k+2} \right\} \supset [\![0;B_k]\!]$ et $\left\{qF_{k+1}-pF_{k-1} \, , \, 0\leqslant q \leqslant F_{k+4} \, , \, 0\leqslant p \leqslant F_{k+2} \right\} \supset [\![-C_k;F_kF_{k+3}]\!]$ ? Mais que valent $B_k$ et $C_k$, et pourquoi ?

    Désolé, je dois sûrement être à côté de la plaque :-(
  • Ne te fatigue plus, analystedudimanche, il m'a fallu un certain temps pour comprendre mais ça y est, j'ai pigé ! Cela colle parfaitement ! En revanche rédiger une démonstration détaillée ne serait pas forcément facile.

    Encore bravo et merci !
  • Un article très intéressant ici (voir pages 10-14).
Connectez-vous ou Inscrivez-vous pour répondre.