The Art Gallery Guardian

Divide and conquer over cyclic groups


Recently we found a divide and conquer algorithm over Zm\Z_m. We have an efficient algorithm for the case where all the elements SS are in Zm\Z_m^*, the set of units.

Our divide and conquer algorithm basically partition the numbers by throwing them into different subgroups. Assume mm has distinct prime factors p1<<pkp_1 < \ldots < p_k, and for simplicity, define p0=1p_0=1. We partition SS to S0,,SkS_0,\ldots,S_k, where SiS_i contain all the elements that's divisible by pip_i but not pjp_j for any j>ij>i. We recursively apply our algorithm to each Si/piS_i/p_i in Zm/pi\Z_{m/p_i} and combine the solution.

This gives us a recurrence relation, and the crucial part of the recurrence involves the following function.

Let pip_i be the iith smallest prime number, and p0p_0 defined as 11. If we know that f0(x)=xf_0(x) = x and fk(x)=i=0kfi(x/pi)f_k(x) = \sum_{i=0}^k f_i(x/p_i), then we can show that fk(x)=xi=1k(1+1pj1)\displaystyle f_k(x) = x \prod_{i=1}^{k} \left(1+\frac{1}{p_j-1}\right) by induction.

First, we would need a small lemma.

Lemma1

Let a1,,aka_1,\ldots,a_k be real numbers such that non of them is 00 or 11, then 1+j=1k1pji=1j(1+1pi1)=j=1k(1+1pj1)\displaystyle 1+\sum_{j=1}^k \frac{1}{p_j} \prod_{i=1}^j \left(1+\frac{1}{p_i -1}\right) = \prod_{j=1}^k \left(1+\frac{1}{p_j-1}\right)

Proof

Proof by induction, basically 1x(1+1x1)=1x1\frac{1}{x} (1+\frac{1}{x-1})=\frac{1}{x-1} for any x0,1x\neq 0,1, so this is true when k=1k=1.

1+j=1k1pji=1j(1+1pi1)=j=1k1(1+1pj1)+1pkj=1k(1+1pj1)=(1+1pk(1+1pk1))j=1k1(1+1pj1)=(1+1pk1)j=1k1(1+1pj1)\displaystyle \begin{aligned} 1+\sum_{j=1}^k \frac{1}{p_j} \prod_{i=1}^j \left(1+\frac{1}{p_i -1}\right) &= \prod_{j=1}^{k-1}\left(1+\frac{1}{p_j-1}\right) + \frac{1}{p_k}\prod_{j=1}^{k}\left(1+\frac{1}{p_j-1}\right)\\ &= \left(1+\frac{1}{p_k} \left(1 + \frac{1}{p_{k-1}}\right) \right)\prod_{j=1}^{k-1}\left(1+\frac{1}{p_j-1}\right)\\ &= \left(1+\frac{1}{p_k -1}\right)\prod_{j=1}^{k-1}\left(1+\frac{1}{p_j-1}\right)\\ \end{aligned}

Theorem2

fk(x)=xi=1k(1+1pi1)\displaystyle f_k(x) = x \prod_{i=1}^{k} \left(1+\frac{1}{p_i-1}\right)

Proof

fk(x)=i=0kfi(x/pi)fk(x)fk(x/pi)=i=0k1fi(x/pi)=xi=0k11pij=1i(1+1pj1)=x(1+i=1k11pij=1i(1+1pj1))=xi=1k1(1+1pi1)\displaystyle \begin{aligned} f_k(x) &= \sum_{i=0}^k f_i(x/p_i)\\ f_k(x)-f_k(x/p_i) &= \sum_{i=0}^{k-1} f_i(x/p_i)\\ &= x \sum_{i=0}^{k-1} \frac{1}{p_i} \prod_{j=1}^i \left(1+\frac{1}{p_j-1}\right)\\ &= x \left(1 + \sum_{i=1}^{k-1} \frac{1}{p_i} \prod_{j=1}^i \left(1+\frac{1}{p_j-1}\right)\right)\\ &= x \prod_{i=1}^{k-1} \left(1+\frac{1}{p_i-1}\right)\\ \end{aligned}

We can substitute fk(x)=xi=1k(1+1pi1)f_k(x) = x \prod_{i=1}^{k} \left(1+\frac{1}{p_i-1}\right), and see the result matches.

x(11pi)i=1k(1+1pi1)=xi=1k1(1+1pi1)\displaystyle \begin{aligned} x\left(1-\frac{1}{p_i}\right) \prod_{i=1}^{k} \left(1+\frac{1}{p_i-1}\right) = x \prod_{i=1}^{k-1} \left(1+\frac{1}{p_i-1}\right) \end{aligned}

It's also useful to bound fk(x)f_k(x).

Theorem3

fk(x)=O(xlogk)\displaystyle f_k(x) = O(x \log k)

Proof

fk(x)=xi=1k(1+1pi1)xexp(i=1k1pi1)xexp(1+i=1k1pi)xexp(loglog(klogk)+A)=O(xlogk)\displaystyle \begin{aligned} f_k(x) &= x \prod_{i=1}^{k} \left(1+\frac{1}{p_i-1}\right)\\ &\leq x \exp \left( \sum_{i=1}^k \frac{1}{p_i-1}\right)\\ &\leq x \exp \left( 1 + \sum_{i=1}^k \frac{1}{p_i}\right)\\ &\leq x \exp \left( \log \log (k \log k) + A \right)\\ &= O(x \log k) \end{aligned}

It uses the facts on sum of reciprocals of the primes.

Apply this to the actual algorithm running time analysis, we would get a O(loglogm)O(\log \log m) blow up of the running time for the Zm\Z_m^* algorithm.

Posted by Chao Xu on .
Tags: .