À quelle vitesse pouvons-nous trouver toutes les combinaisons de quatre carrés qui résument à N?

Une question a été posée à Stack Overflow ( ici ):

Compte tenu d' un nombre entier , imprimer toutes les combinaisons possibles des valeurs entières de et qui résolvent l'équation .A , B , C D A 2 + B 2 + C 2 + D 2 = $N$$A,B,C$$D$$A^2+B^2+C^2+D^2 = N$

Cette question est bien sûr liée à la conjecture de Bachet en théorie des nombres (parfois appelée théorème des quatre carrés de Lagrange en raison de sa preuve). Il y a des articles qui expliquent comment trouver une solution unique, mais je n'ai pas pu trouver quoi que ce soit qui parle de la vitesse à laquelle nous pouvons trouver toutes les solutions pour un particulier (c'est-à-dire toutes les combinaisons , pas toutes les permutations ).$N$

J'y ai beaucoup réfléchi et il me semble que cela peut être résolu dans le temps et l'espace $O(N)$ , où $N$ est la somme souhaitée. Cependant, faute d'informations préalables sur le sujet, je ne sais pas s'il s'agit d'une revendication significative de ma part ou simplement d'un résultat trivial, évident ou déjà connu.

Donc, la question est alors, à quelle vitesse pouvons-nous trouver toutes les sommes des quatre carrés pour un N donné $N$?

OK, voici l'algorithme (presque) O (N) auquel je pensais. Deux premières fonctions de support, une fonction de racine carrée entière la plus proche:

    // the nearest integer whose square is less than or equal to N
    public int SquRt(int N)
    {
        return (int)Math.Sqrt((double)N);
    }

Et une fonction pour renvoyer toutes les paires TwoSquare sommant de 0 à N:

    // Returns a list of all sums of two squares less than or equal to N, in order.
    public List<List<int[]>> TwoSquareSumsLessThan(int N)
    {
        //Make the index array
        List<int[]>[] Sum2Sqs = new List<int[]>[N + 1];

        //get the base square root, which is the maximum possible root value
        int baseRt = SquRt(N);

        for (int i = baseRt; i >= 0; i--)
        {
            for (int j = 0; j <= i; j++)
            {
                int sum = (i * i) + (j * j);
                if (sum > N)
                {
                    break;
                }
                else
                {
                    //make the new pair
                    int[] sumPair = { i, j };
                    //get the sumList entry
                    List<int[]> sumLst;
                    if (Sum2Sqs[sum] == null)
                    {   
                        // make it if we need to
                        sumLst = new List<int[]>();
                        Sum2Sqs[sum] = sumLst;
                    }
                    else
                    {
                        sumLst = Sum2Sqs[sum];
                    }
                    // add the pair to the correct list
                    sumLst.Add(sumPair);
                }
            }
        }

        //collapse the index array down to a sequential list
        List<List<int[]>> result = new List<List<int[]>>();
        for (int nn = 0; nn <= N; nn++)
        {
            if (Sum2Sqs[nn] != null) result.Add(Sum2Sqs[nn]);
        }

        return result;
    }

Enfin, l'algorithme lui-même:

    // Return a list of all integer quads (a,b,c,d), where:
    //      a^2 + b^2 + c^2 + d^2 = N,
    // and  a >= b >= c >= d,
    // and  a,b,c,d >= 0
    public List<int[]> FindAllFourSquares(int N)
    {
        // get all two-square sums <= N, in descending order
        List<List<int[]>> Sqr2s = TwoSquareSumsLessThan(N);

        // Cross the descending list of two-square sums <= N with
        // the same list in ascending order, using a Merge-Match
        // algorithm to find all combinations of pairs of two-square
        // sums that add up to N
        List<int[]> hiList, loList;
        int[] hp, lp;
        int hiSum, loSum;
        List<int[]> results = new List<int[]>();
        int prevHi = -1;
        int prevLo = -1;

        //  Set the Merge sources to the highest and lowest entries in the list
        int hi = Sqr2s.Count - 1;
        int lo = 0;

        //  Merge until done ..
        while (hi >= lo)
        {
            // check to see if the points have moved
            if (hi != prevHi)
            {
                hiList = Sqr2s[hi];
                hp = hiList[0];     // these lists cannot be empty
                hiSum = hp[0] * hp[0] + hp[1] * hp[1];
                prevHi = hi;
            }
            if (lo != prevLo)
            {
                loList = Sqr2s[lo];
                lp = loList[0];     // these lists cannot be empty
                loSum = lp[0] * lp[0] + lp[1] * lp[1];
                prevLo = lo;
            }

            // do the two entries' sums together add up to N?
            if (hiSum + loSum == N)
            {
                // they add up, so cross the two sum-lists over each other
                foreach (int[] hiPair in hiList)
                {
                    foreach (int[] loPair in loList)
                    {
                        // make a new 4-tuple and fill it
                        int[] quad = new int[4];
                        quad[0] = hiPair[0];
                        quad[1] = hiPair[1];
                        quad[2] = loPair[0];
                        quad[3] = loPair[1];

                        // only keep those cases where the tuple is already sorted
                        //(otherwise it's a duplicate entry)
                        if (quad[1] >= quad[2]) //(only need to check this one case, the others are implicit)
                        {
                            results.Add(quad);
                        }
                        //(there's a special case where all values of the 4-tuple are equal
                        // that should be handled to prevent duplicate entries, but I'm
                        // skipping it for now)
                    }
                }
                // both the HI and LO points must be moved after a Match
                hi--;
                lo++;
            }
            else if (hiSum + loSum < N)
            {
                lo++;   // too low, so must increase the LO point
            }
            else    // must be > N
            {
                hi--;   // too high, so must decrease the HI point
            }
        }
        return results;
    }

Comme je l'ai déjà dit, il devrait être assez proche de O (N), cependant, comme le souligne Yuval Filmus, car le nombre de solutions à quatre carrés de N peut être d'ordre (N ln ln N), alors cet algorithme ne pourrait pas être moins que ça.

L'algorithme de Juho peut être amélioré en un algorithme en utilisant la rencontre au milieu. Passez en revue toutes les paires ; pour chaque paire telle que , stockez dans un tableau de longueur (chaque position pourrait contenir plusieurs paires, qui pourraient être stockées dans une liste chaînée). Parcourez maintenant les paires telle sorte que les cellules correspondantes dans soient pas vides.A , B ≤ $O(N)$ M=A2+B2≤N(A,B)TNMM,N-M$A,B \leq \sqrt{N}$$M=A^2+B^2 \leq N$$(A,B)$$T$$N$$M$$M,N-M$$T$

De cette façon, nous obtenons une représentation implicite de tous les quadruples. Si nous voulons tous les énumérer, nous ne pouvons pas faire mieux que , car le théorème des quatre carrés de Jacobi montre que (pour impair ) le nombre de représentations est , et il existe une infinité de nombres entiers tels que (voir le théorème de Grönwall ).$\Omega(N\log\log N)$$N$$8\sigma(N)$$\sigma(N) \geq (e^\gamma - \epsilon) N\log\log N$

Afin d'obtenir des algorithmes moins triviaux, on peut essayer de factoriser sur l'anneau de quaternion approprié, car on sait que les représentations sous forme de sommes de deux carrés correspondent (dans un certain sens) à ces factorisations, à travers l'identité quadratique de Lagrange. Il nous faudrait encore trouver toutes les représentations de tout nombre premier pertinent.$N$

Je pense qu'un algorithme de temps n'est pas trivial et nécessite un aperçu s'il en existe un. L'algorithme évident qui s'exécute en temps quadratique énumère tous les tuples . Cela peut être fait en quatre boucles, de sorte que la complexité temporelle totale devient . Il énumère également clairement toutes les solutions.$o(N^2)$$A,B,C,D \leq \sqrt[]{N}$$O(N^2)$

En tant qu'algorithmes relatifs, Rabin et Shallit [1] présentent deux algorithmes randomisés pour décomposer des entiers en somme de carrés. Pour deux carrés, ils donnent un algorithme de temps attendu . Pour quatre carrés, ils donnent un algorithme de temps attendu . Notez que les algorithmes ne vous donnent pas toutes les solutions, mais seulement une seule.O ( log 2 n log log n $O(\log^2 n)$$O(\log^2 n \log \log n)$

[1] MO Rabin, JO Shallit, Algorithmes randomisés en théorie des nombres , Communications on Pure and Applied Mathematics 39 (1986), no. S1, p. S239 – S256 .

Le nombre de solutions est exactement , où passe par tous les diviseurs de qui ne sont pas des multiples de 4. C'est un théorème de Jacobi.d $8\sum d$$d$$n$