Matryoshka Sequences

From Polymath1Wiki
Jump to: navigation, search

A Matryoshka sequence is a combination of a function [math]f:\{1,2,\dots,m-1\}\to \mathbb{C}[/math] and a complex number [math]\epsilon[/math]. To wit, set

[math] F(x):=f(x \bmod m)[/math] if [math] x [/math] is not a multiple of [math]m[/math], and
[math] F(x) := \epsilon F(x/m)[/math] if [math] x [/math] is a multiple of [math]m[/math].

Examples

Walters' example [math] \lambda_3 [/math]

The most straightforward example is [math]\lambda_3[/math], the multiplicative sequence sending primes to 1 or -1 according to whether they are congruent to 1 or -1 modulo 3, and sending 3 to 1. This is the Matryoshka sequence from [math]m=3, f(1)=-f(2)=1,\epsilon = 1 [/math]. We have the pleasant formula:

[math] \sum_{j=1}^k \lambda_3(jd) = \lambda(d) \sum_{j=1}^k \lambda_3(j) = \lambda_3(d) S(k),[/math]

where [math]S(k)[/math] is the number of `1's in the ternary expansion of k. The discrepancy therefore satisfies

[math]\delta(N,\lambda_3) \leq \log_3(2N+1) \lt \log_3(N)+1[/math]

with equality infinitely often.

Legendre symbol [math] \lambda_p [/math]

See paper of Borwein, et al.

Improved Walters [math] \mu_3 [/math]

Define [math] \mu_3 [/math] by taking [math]\displaystyle m=3, f(1)=-f(2)=1, \epsilon = -1[/math]. This function is multiplicative. We have the pleasant formula:

[math] \sum_{j=1}^k \mu_3(jd) = \mu_3(d) \sum_{j=1}^k \mu_3(j) = \mu_3(d) S(k) [/math]

where [math]S(k)[/math] is the number of `1's in the ternary expansion of [math]k[/math] in even position, minus the number of `1's in odd position. The discrepancy therefore satisfies

[math] \delta(N,\mu_3) \leq \log_9(8N+1) \lt \log_9(N) + 1 [/math]

with equality infinitely often.

Generalized Walters [math] \mu_p [/math]

Fix an odd prime [math]p[/math], and let [math]\displaystyle \omega=\exp(2\pi i /(p-1))[/math]. Then $\mu_p$ is the Matryoshka sequence from [math]\displaystyle m=p,f(j)=\omega^{j-1}, \epsilon=\omega[/math]. This coincides with the Improved Walters for $p=3$, but is not multiplicative for [math]p\gt3[/math]. We have the pleasant formula

[math] \sum_{j=1}^k \mu_p(j) = \sum_{r=0}^{\ell} \omega^r \sum_{j=1}^{b_r} \omega^{j-1} [/math]

where [math]k= b_0+b_1 p + b_2 p^2 + \dots+b_{\ell}p^{\ell}[/math] (all of the [math]b_r[/math] are in [math]\{0,1,\dots,p-1\}[/math], and [math] \ell=\lfloor \log_p k \rfloor[/math]). We can rewrite the above sum as

[math] \sum_{r=0}^{\ell} \omega^r \sum_{j=1}^{b_r} \omega^{j-1} = \sum_{s=0}^{\ell'} \sum_{r=0}^{p-2} \omega^r \sum_{j=1}^{b_{r+s(p-1)}} \omega^{j-1}, [/math]

with [math]\ell' = \lfloor \log_{p^{p-1}}k \rfloor[/math]. Set [math]M_p[/math] to be the maximum of [math]\left|\sum_{r=0}^{p-2} \omega^r \sum_{j=1}^{\beta_r} \omega^{j-1}\right|[/math] where [math]\beta_r[/math] is in [math]\{0,1,\dots,p-1\}[/math]. We now have

[math] \left| \sum_{j=1}^k \mu_p(j) \right| \leq (1+\log_{p^{p-1}}k) M_p [/math],

so what is [math] M_p [/math]? As in the comments in this thread, [math] M_p \gtrsim c p^2[/math], so that the discrepancy

[math] \delta(N,\mu_p) \geq \frac{cp^2}{(p-1)\log(p)} \log N. [/math]

Formulas to assist in the handling of Matryoshka sequences

Let [math] m'=m/\gcd(d,m), M = \lfloor k/m' \rfloor m' [/math]. Then

[math] \sum_{i=1}^k F(id) = \sum_{i=1}^{k-M} f(id \bmod m) + \sum_{i=1}^{\lfloor k/m' \rfloor} F(i d/ \gcd(d,m))[/math]

Source code

Mathematica code for generating the terms of [math] \mu_p(k) [/math].

   \[Mu][p_, k_] := \[Mu][p, k] = 
      Block[{\[Omega] = Exp[2 \[Pi] I / (p - 1)]}, 
         Which[1 <= k < p, \[Omega]^(k - 1),
         Mod[k, p] == 0, \[Omega] \[Mu][k/p] ,
         True, \[Mu][Mod[k, p, 1]]]];

Mathematica code for [math] \sum_{i=j}^k \mu_p(j) [/math].

    SumFormulaForMu[p_,k_]:=
      Module[
       {j,bj,bseq},
       j=IntegerExponent[k,p];
       bj=Mod[k/p^j,p];
       bseq=Reverse[IntegerDigits[k,p]];
       Table[\[Omega]^r,{r,0,Length[bseq]-1}].(Sum[\[Omega]^(j-1),{j,1,#}]&/@bseq)]