Matryoshka Sequences

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

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

[math]\displaystyle{ F(x) := \epsilon F(x/m) }[/math] if [math]\displaystyle{ x }[/math] is a multiple of [math]\displaystyle{ m }[/math].

Examples

Walters' example [math]\displaystyle{ \lambda_3 }[/math]

The most straightforward example is [math]\displaystyle{ \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]\displaystyle{ m=3, f(1)=-f(2)=1,\epsilon = 1 }[/math]. We have the pleasant formula:

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

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

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

with equality infinitely often.

Legendre symbol [math]\displaystyle{ \lambda_p }[/math]

See paper of Borwein, et al.

Improved Walters [math]\displaystyle{ \mu_3 }[/math]

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

[math]\displaystyle{ \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]\displaystyle{ S(k) }[/math] is the number of `1's in the ternary expansion of [math]\displaystyle{ k }[/math] in even position, minus the number of `1's in odd position. The discrepancy therefore satisfies

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

with equality infinitely often.

Generalized Walters [math]\displaystyle{ \mu_p }[/math]

Fix an odd prime [math]\displaystyle{ p }[/math], and let [math]\displaystyle{ \displaystyle \omega=\exp(2\pi i /(p-1)) }[/math]. Then $\mu_p$ is the Matryoshka sequence from [math]\displaystyle{ \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]\displaystyle{ p\gt 3 }[/math]. We have the pleasant formula

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

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

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

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

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

[math]\displaystyle{ \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]\displaystyle{ m'=m/\gcd(d,m), M = \lfloor k/m' \rfloor m' }[/math]. Then

[math]\displaystyle{ \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]\displaystyle{ \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]\displaystyle{ \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)]