полная система вычетов?

[maxal]

Пусть $N=2^{127}-1$. Докажите или опровергните, что числа $\sum_{i=0}^{126} \alpha_i 5^i$, где $\alpha_i \in \{0,1\}$, представляют каждый вычет по модулю $N$ хотя бы раз.

[waxtep]

Можно понаблюдать за более скромными $N$, например, для $N=2^7-1$ выяснится, что $5^0+5^1+5^4+5^6\equiv0\pmod{N}$, и, значит, результат будет одинаковым, если разместить нули или единички на соответствующих местах, и полной системы вычетов не получится. Аналогично, для $N=2^8-1, 5^1+5^4+5^5+5^6\equiv0\pmod{N}$. Если удастся подобную сумму и для заданного $N=2^{127}-1$ построить, то докажем, что полной системы не будет

-- 30.05.2024, 22:56 --

Или, ещё более хитрый вариант для $N=2^9-1$, там $5^5+5^7\equiv5^0\pmod{N}$, и значит единичка в нулевой позиции эквивалентна единичкам в пятой и седьмой

-- 30.05.2024, 23:21 --

$N=2^{13}-1:5^2+5^4+5^5\equiv5^0+5^3+5^6+5^7\pmod{N}$. В общем, есть ощущение, что "всегда можно что-то намутить"

[maxal]

waxtep в сообщении #1640791 писал(а):

Если удастся подобную сумму и для заданного $N=2^{127}-1$ построить, то докажем, что полной системы не будет

Мне это не удалось, но было бы интересно увидеть такое вычислительное решение, если кто-то сумеет его построить.
Однако, у задачи есть решение без использования компьютера.

[Vadim32]

Есть такой вариант. Мы сравниваем два множества. Первое множество это множество всех вычетов N. Второе множество, это множество всех вычетов полученных из каждого полинома разрядности 127 с основанием 5. Так как основание простое число, то работаем в поле вычетов основания. Количество элементов второго множества на единицу больше, чем количество элементов всех вычетов. Для сравнения множеств будем использовать две контрольные суммы. В качестве первой суммы мы используем просто сумму всех элементов. Если множества отличаются только на один элемент, разница между суммой первого и суммой второго множества будет показывать какой элемент входит в состав второго множества дважды. Второй контрольной суммой можно использовать сумму квадратов каждого элемента. Разница в этом случае покажет квадрат лишнего элемента, входящего дважды во второе множество. Если квадрат лишнего элемента найденного как разницу первых контрольных сумм даст разницу между вторым контрольными суммами, то это подтвердит(но не докажет) гипотезу о том, что второе множество отличается от первого единственным лишним элементом. Но если гипотеза не подтвердится, то это доказывает что, множества отличаются более чем на один элемент, и не для каждого вычета существует соответствующий полином. Именно это демонстрирует программа.
Запустив программу можно посмотреть результат

127: N=170141183460469231731687303715884105727
poly_sum1=80280682861595619370168968130363211378
sum1=0
d1=80280682861595619370168968130363211378
poly_sum2=155729045835901150045551746619023564571
sum2=0
d2=155729045835901150045551746619023564571
d2-d1*d1=31765023455761517083774786768884716470
Error!

Программой можно подтвердить равенство для 2 и 3 бит. Для 6 бит подтверждение ложное. Для остальных битностей равенство не подтверждается.

Используется синтаксис C++

#include <iostream>
#include <boost/multiprecision/cpp_int.hpp>
using namespace std;
using namespace boost::multiprecision;

template <class T>
T calculate_sum1(T max_value)
{
   return  max_value*(max_value+1)/2;
}

template <class T>
T calculate_sum2(T max_value)
{  T s1=max_value;
   T s2=s1*max_value;
   T s3=s2*max_value;
   return  (max_value + 3*s2 + 2*s3)/6;
}

template <class T, int BASE>
class BINARY_POLY
{ 
public:
   const int NBIT;
   const T NITEMS;
   const T N;
   T *digit;

   BINARY_POLY(int nbit):NBIT(nbit),NITEMS(pow((T)2,nbit)), N(NITEMS-1), digit(new T[nbit]) 
   {  T d=1;
      for(int nb=0; nb<NBIT; nb++)
      {  digit[nb]=d;
         d=(d*BASE) % N;
      }
   }
   ~BINARY_POLY()
   {  delete digit;
   }

   T calculate_sum1(int ndigits)
   {  
      T digit_sum=0;
      for(int nb=0; nb<ndigits; nb++)
      { 
         digit_sum+=digit[nb];
      }
      T number_of_items=pow((T)2, ndigits-1);

      return ((digit_sum % N)  * number_of_items) % N;
   }

   T calculate_sum1()
   {  return calculate_sum1(NBIT);
   }

   T calculate_sum2(int ndigits)
   {  
      if (ndigits==1)  
      {  return 1;
      }
      else
      {  T n_items=pow((T)2,ndigits-1);
         T d=digit[ndigits-1];
         T s1=calculate_sum1(ndigits-1);
         T s2=calculate_sum2(ndigits-1);
         T S =  ((d*d)% N)*n_items + (2*d*s1  +   s2  + s2);

         return S % N;
      }
   }
   
   T calculate_sum2()
   {  return calculate_sum2(NBIT);
   }
};


int main(int argc, char* argv[])
{
   for(int nb=127; nb<128; nb++)
   {  
      typedef uint512_t T;
      BINARY_POLY<T,5> poly(nb);
      cout << nb << ": " << "N="<< poly.N<< endl; 
      
      T sum1=calculate_sum1(poly.N-1)  % poly.N;
      T poly_sum1=poly.calculate_sum1();
      T delta_sum1=(poly_sum1  + poly.N - sum1) % poly.N;
      cout << " poly_sum1=" << poly_sum1 << endl;
      cout << " sum1=" << sum1 << endl;
      cout << " d1=" << (poly_sum1 + poly.N - sum1) % poly.N <<endl;

      T sum2=calculate_sum2(poly.N-1) % poly.N;
      T poly_sum2=poly.calculate_sum2();
      T delta_sum2=(poly_sum2 + poly.N - sum2) % poly.N;
      cout << " poly_sum2=" << poly_sum2 << endl;
      cout << " sum2=" << sum2 << endl;
      cout << " d2=" << (poly_sum2 + poly.N - sum2) % poly.N <<endl;
      
      T d=((delta_sum1*delta_sum1) % poly.N  + poly.N - delta_sum2) % poly.N;
      cout << " d2-d1*d1=" << d <<endl;
      cout << (d? " Error!" : " No error found") ;
      cout << endl << endl;
   }
        return 0;
}

[maxal]

Vadim32
Перефразируя ваш текст, вы тестируете сравнение

$$\sum_{\alpha\in\{0,1\}^{127}} (\sum_{i=0}^{126} \alpha_i 5^i)^2 \equiv \big(\sum_{\alpha\in\{0,1\}^{127}} \sum_{i=0}^{126} \alpha_i 5^i\big)^2 \pmod N.$$

Нетрудно видеть, что правая часть это просто

$$\big( \frac{5^{127}-1}8\big)^2 \pmod N,$$

а левая часть раскрывается в

$$\sum_{\alpha\in\{0,1\}^{127}} \sum_{i,j=0}^{126} \alpha_i\alpha_j 5^{i+j} \equiv \frac14 \sum_{i,j=0\atop i\ne j}^{126} 5^{i+j} + \frac12 \sum_{i=0}^{126} 5^{2i} \equiv \big( \frac{5^{127}-1}8\big)^2 + \frac{5^{254}-1}{96}\pmod N.$$

Так как $\frac{5^{254}-1}{96}\not\equiv 0\pmod N$, то ответ на вопрос задачи отрицательный.

Однако, ваше значение d2-d1*d1=31765023455761517083774786768884716470 не совпадает с $\frac{5^{254}-1}{96}\bmod N = 138376160004707714647912516946999389257$. Ищите ошибку в своем коде.

[Vadim32]

Да, пишу одно, делаю другое, отсюда и знак минус потерян.
вот исправление

Используется синтаксис C++

int main(int argc, char* argv[])
{
   for(int nb=127; nb<128; nb++)
   {  
      typedef uint512_t T;
      BINARY_POLY<T,5> poly(nb);
      cout << nb << ": " << "N="<< poly.N<< endl; 
      
      T sum1=calculate_sum1(poly.N-1)  % poly.N;
      T poly_sum1=poly.calculate_sum1();
      T delta_sum1=(poly_sum1  + poly.N - sum1) % poly.N;
      cout << " poly_sum1=" << poly_sum1 << endl;
      cout << " sum1=" << sum1 << endl;
      cout << " d1=" << delta_sum1 <<endl;

      T sum2=calculate_sum2(poly.N-1) % poly.N;
      T poly_sum2=poly.calculate_sum2();
      T delta_sum2=(poly_sum2 + poly.N - sum2) % poly.N;
      cout << " poly_sum2=" << poly_sum2 << endl;
      cout << " sum2=" << sum2 << endl;
      cout << " d2=" << delta_sum2 <<endl;
      
      //T d=((delta_sum1*delta_sum1) % poly.N  + poly.N - delta_sum2) % poly.N;
      T d=(delta_sum2 + poly.N - (delta_sum1*delta_sum1) % poly.N   ) % poly.N;
      cout << " d2-d1*d1=" << d <<endl;
      cout << (d? " Error!" : " No error found") ;
      cout << endl << endl;
   }
        return 0;
}

и вот результат:

127: N=170141183460469231731687303715884105727
poly_sum1=80280682861595619370168968130363211378
sum1=0
d1=80280682861595619370168968130363211378
poly_sum2=155729045835901150045551746619023564571
sum2=0
d2=155729045835901150045551746619023564571
d2-d1*d1=138376160004707714647912516946999389257
Error!


Но всё же я не только тестирую сравнения, я ещё и вычитаю суммы первого множества. Понятно, что сумма вычетов всегда даст ноль для простого числа, но вот сумма квадратов, как-то не очевидно - всегда ли будет ноль, думаю нет.

[maxal]

Vadim32 в сообщении #1641111 писал(а):

но вот сумма квадратов, как-то не очевидно - всегда ли будет ноль, думаю нет

Будет, как и для любой другой степени не кратной $p-1$. Это легко вывести из существования первообразного корня по модулю $p$.

[lel0lel]

Без компьютера)
$p=127, N=2^p-1\in \mathbb{P}$. Определяются множества: $A=\{\sum_{i=1}^{p-1} \alpha_i 5^i \bmod N \mid \alpha_i \in\{0,1\}\}$, $B=\{ (1+a) \bmod N \mid a\in A\}$. Это множества вычетов, полученные из исходных чисел, имеющих $\alpha_0=0$ и $\alpha_0=1$, соответственно. Нетрудно видеть что
1. если $a\in A$, то $a+1\in B$
2. если $b\in B$, то $b-1\in A$
Тогда полная система вычетов образуется только если упорядоченные остатки исходных чисел образуют следующую "структуру":
$\{A,B,A,B,\ldots,A,(B,A),B,A,\ldots,B\}$, что соответствует $\{0,1,2,3,\ldots,y-1,(y,y),y+1,y+2,\ldots,N-1\}$, при этом $|A|=|B|=2^{p-1}$, $|A\cap B|=1$. Здесь $(B,A)$ означает, что два исходных различных числа попадают в один класс вычетов $y$. Позиция $(B,A)$ в списке пока неизвестна, в принципе, это может быть первый элемент списка ($y=0$), а вот последним быть не может (иначе первый элемент тоже пара). Также понятно, что никаких $(A,A)$ в списке быть не может, по причине последующих за ними $(B,B)$. В общем-то, $y$ выше уже находили через сумму всех чисел, но можно и так: пара $(A,B)$ только в том случае не "сгенерирует" другие пары $(A,B)$, если в числах, из которых она получена, нули и единички проживают в несовпадающих позициях. Поэтому $2y\equiv \sum_{i=0}^{p-1}5^i \equiv\frac{5^p-1}{4}\pmod N$. Значение $y$ без компьютера не вычислить, поэтому нужно обратить внимание на обсуждаемую "структуру". Если идти в ней по возрастанию вычетов, принадлежащих $A$, то чётность вычетов меняется только один раз, это происходит на вычете $y$. С другой стороны, в нашем случае есть немало представителей $A$ различной чётности: $0,5,30,125,130,155...$ Следовательно, как минимум четыре вычета полной системы вычетов получить нельзя.