пусть A — верхнетреугольная матрица, с которой мы начинали (единицы стоят там, где j делит i), тогда M(n) — это просто значение первой переменной в решении системы Ax = (1…1), посчитанное при помощи правила Крамера
то есть чтобы посчитать M(n), полезно обратить матрицу A — а для этого полезно понять какой у нее смысл, с каким оператором она связана
A^t — это матрица суммирования по делителям; обратная операция к суммированию по делителям хорошо известна — это свертка с функцией Мёбиуса (μ=(-1)^s для произведения s различных простых, 0 иначе)
отсюда получаем, что M(n) — это сумма μ(k) по k от 1 до n
в частности, ясно, что |M(n)| не превосходит n (т.к. |μ|⩽1); кстати, оценка |M(n)|=o(n) эквивалентна теореме о распределении простых чисел (количество простых до n ~ n/log(n)) — в общем, связь этих определителей с аналитической теорией чисел перестает казаться такой уж загадочной
но тут самое время сделать паузу в разговорах и это вычисление M(n) реализовать:
import numpy as np
import matplotlib.pyplot as plt
def primes(N):
is_prime = np.ones(N+1)
is_prime[:2] = 0
for n in range(int(np.sqrt(N))+1):
if is_prime[n]:
is_prime[n*n::n] = 0
return np.nonzero(is_prime)[0]
N = 3*10**6
moebius = np.ones(N+1)
for p in primes(N):
moebius[::p] *= -1
moebius[::p**2] = 0
mertens = np.cumsum(moebius)
mertmax = np.maximum.accumulate(np.abs(mertens[1:]))
ax = plt.axes()
ax.plot(range(1,N+1),mertens[1:])
ax.plot(range(1,N+1),np.sqrt(range(1,N+1)),-np.sqrt(range(1,N+1)))
ax.plot(range(1,N+1),mertmax,-mertmax)
plt.xlim(0,None)
plt.show()
функция Мёбиуса принимает значения ±1 довольно хаотичным образом, поэтому можно ожидать чего-то в духе закона повторного логарифма (который выполнялся бы, если бы mu действительно генерировалась подкидываниями монетки), что максимум |M(n)| мог бы расти примерно как √n × (log log n)^(1/2)… есть гипотеза, что в реальности он растет примерно как √n × (log log log n)^(5/4) (а гипотеза Римана эквивалентна оценке √n O(n^ε) для всех ε>0)
(ситуация напоминает обсуждавшуюся в https://t.me/compmathweekly/18 — с математической точки зрения кратные логарифмы стремятся к бесконечности, но увидеть это в компьютерном эксперименте практически невозможно, уже двойной логарифм везде выглядит как ограниченная функция)
и доказано, что для каких-то n функция Мёртенса M(n) принимает значение, большее по модулю чем √n… но оценка сверху на первое такое n — что-то типа 10^(10^60) (!), а для всех реально вычисленных значений |M(n)|/√n < 0.6