Как быстро мы можем найти все комбинации четырех квадратов, которые суммируются с N?

Вопрос был задан при переполнении стека ( здесь ):

Принимая во внимание целое число , распечатать все возможные комбинации целочисленных значений и , которые решают уравнение .$N$D A 2 + B 2 + C 2 + D 2 = $A,B,C$$D$$A^2+B^2+C^2+D^2 = N$

Этот вопрос, конечно, связан с гипотезой Бахе в теории чисел (иногда называемой теоремой Лагранжа о четырех квадратах из-за его доказательства). Есть несколько работ, в которых обсуждается, как найти единственное решение, но я не смог найти ничего, что говорило бы о том, как быстро мы можем найти все решения для конкретного (то есть всех комбинаций , а не всех перестановок ).$N$

Я много думал об этом, и мне кажется, что это можно решить за времени и пространства, где - желаемая сумма. Однако, не имея какой-либо предварительной информации по этому вопросу, я не уверен, является ли это значительным заявлением с моей стороны или просто тривиальным, очевидным или уже известным результатом.$O(N)$$N$

Итак, вопрос в том, как быстро мы можем найти все суммы четырех квадратов для данного ?$N$

Хорошо, вот алгоритм (почти) O (N), о котором я думал. Первые две вспомогательные функции, ближайшая целочисленная функция квадратного корня:

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

И функция для возврата всех пар TwoSquare, суммирующих от 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;
    }

Наконец, сам алгоритм:

    // 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;
    }

Как я уже говорил ранее, он должен быть довольно близок к O (N), однако, как указывает Ювал Фильмус, поскольку число решений четырех квадратов для N может быть порядка (N ln ln N), тогда этот алгоритм не может быть меньше этого.

Алгоритм Джухо может быть улучшен до алгоритма с использованием встречи в середине. Обойти все пары ; для каждой пары, такой что , сохранить в некотором массиве длины (каждая позиция может содержать несколько пар, которые могут храниться в связанном списке). Теперь перейдем к парам так, чтобы соответствующие ячейки в были непустыми.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$

Таким образом, мы получаем неявное представление всех четверок. Если мы хотим перечислить все из них, то мы не можем сделать ничего лучше, чем , поскольку теорема Якоби о четырех квадратах показывает, что (для нечетного ) число представлений равно , и существует бесконечно много целых чисел, таких что (см. Теорему Гронуолла ).N 8 σ ( N ) σ ( N ) ≥ ( e γ - ϵ ) N log log $\Omega(N\log\log N)$$N$$8\sigma(N)$$\sigma(N) \geq (e^\gamma - \epsilon) N\log\log N$

Чтобы получить менее тривиальные алгоритмы, можно попытаться разложить по соответствующему кольцу кватернионов, поскольку мы знаем, что представления в виде сумм двух квадратов соответствуют (в некотором смысле) этим факторизациям через тождество Лагранжа из четырех квадратов. Нам все еще нужно найти все представления любого соответствующего простого числа.$N$

Я думаю, что алгоритм времени не является тривиальным и требует некоторого понимания, если таковой существует. Очевидный алгоритм, который работает в квадратичном времени, перечисляет все кортежи . Это можно сделать в четыре цикла, поэтому общая сложность времени становится . Также четко перечисляются все решения.A , B , C , D ≤ $o(N^2)$ O(N2$A,B,C,D \leq \sqrt[]{N}$$O(N^2)$

В качестве взаимосвязанных алгоритмов Рабин и Шаллит [1] представляют два рандомизированных алгоритма для разложения целых чисел в виде суммы квадратов. Для двух квадратов они дают алгоритм ожидаемого времени . Для четырех квадратов они дают алгоритм ожидаемого времени . Обратите внимание, что алгоритмы не дают вам все решения, а только одно.O ( log 2 n log log n $O(\log^2 n)$$O(\log^2 n \log \log n)$

[1] М.О. Рабин, Дж. О. Шаллит, Рандомизированные алгоритмы в теории чисел , Сообщения по чистой и прикладной математике 39 (1986), №. S1, стр. S239 – S256 .

Число решений ровно , где пробегает все делители которые не кратны 4. Это теорема Якоби.d $8\sum d$$d$$n$