# Divide and conquer over cyclic groups

Recently we found a divide and conquer algorithm over $Z_{m}$. We have an efficient algorithm for the case where all the elements $S$ are in $Z_{m}$, the set of units.

Our divide and conquer algorithm basically partition the numbers by throwing them into different subgroups. Assume $m$ has distinct prime factors $p_{1}<…<p_{k}$, and for simplicity, define $p_{0}=1$. We partition $S$ to $S_{0},…,S_{k}$, where $S_{i}$ contain all the elements that’s divisible by $p_{i}$ but not $p_{j}$ for any $j>i$. We recursively apply our algorithm to each $S_{i}/p_{i}$ in $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 $p_{i}$ be the $i$th smallest prime number, and $p_{0}$ defined as $1$. If we know that $f_{0}(x)=x$ and $f_{k}(x)=∑_{i=0}f_{i}(x/p_{i})$, then we can show that $f_{k}(x)=xi=1∏k (1+p_{j}−11 )$ by induction.

First, we would need a small lemma.

Let $a_{1},…,a_{k}$ be real numbers such that non of them is $0$ or $1$, then $1+j=1∑k p_{j}1 i=1∏j (1+p_{i}−11 )=j=1∏k (1+p_{j}−11 )$

Proof by induction, basically $x1 (1+x−11 )=x−11 $ for any $x=0,1$, so this is true when $k=1$.

$1+j=1∑k p_{j}1 i=1∏j (1+p_{i}−11 ) =j=1∏k−1 (1+p_{j}−11 )+p_{k}1 j=1∏k (1+p_{j}−11 )=(1+p_{k}1 (1+p_{k−1}1 ))j=1∏k−1 (1+p_{j}−11 )=(1+p_{k}−11 )j=1∏k−1 (1+p_{j}−11 ) $

$f_{k}(x)=xi=1∏k (1+p_{i}−11 )$

$f_{k}(x)f_{k}(x)−f_{k}(x/p_{i}) =i=0∑k f_{i}(x/p_{i})=i=0∑k−1 f_{i}(x/p_{i})=xi=0∑k−1 p_{i}1 j=1∏i (1+p_{j}−11 )=x(1+i=1∑k−1 p_{i}1 j=1∏i (1+p_{j}−11 ))=xi=1∏k−1 (1+p_{i}−11 ) $

We can substitute $f_{k}(x)=x∏_{i=1}(1+p_{i}−11 )$, and see the result matches.

$x(1−p_{i}1 )i=1∏k (1+p_{i}−11 )=xi=1∏k−1 (1+p_{i}−11 ) $

It’s also useful to bound $f_{k}(x)$.

$f_{k}(x)=O(xgk)$

$f_{k}(x) =xi=1∏k (1+p_{i}−11 )≤xexp(i=1∑k p_{i}−11 )≤xexp(1+i=1∑k p_{i}1 )≤xexp(gg(kgk)+A)=O(xgk) $

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(ggm)$ blow up of the running time for the $Z_{m}$ algorithm.