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} < \dots < p_{k}$ , and for simplicity, define $p_{0} = 1$ . We partition $S$ to $S_{0}, \dots, 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) = \sum_{i = 0}^{k} f_{i} (x / p_{i})$ , then we can show that $f_{k} (x) = x i = 1 \prod k (1 + \frac{1}{p _{j} - 1})$ by induction.

First, we would need a small lemma.

Lemma1

Let $a_{1}, \dots, a_{k}$ be real numbers such that non of them is $0$ or $1$ , then $1 + j = 1 \sum k \frac{1}{p _{j}} i = 1 \prod j (1 + \frac{1}{p _{i} - 1}) = j = 1 \prod k (1 + \frac{1}{p _{j} - 1})$

Proof

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

$1 + j = 1 \sum k \frac{1}{p _{j}} i = 1 \prod j (1 + \frac{1}{p _{i} - 1}) = j = 1 \prod k - 1 (1 + \frac{1}{p _{j} - 1}) + \frac{1}{p _{k}} j = 1 \prod k (1 + \frac{1}{p _{j} - 1}) = (1 + \frac{1}{p _{k}} (1 + \frac{1}{p _{k - 1}})) j = 1 \prod k - 1 (1 + \frac{1}{p _{j} - 1}) = (1 + \frac{1}{p _{k} - 1}) j = 1 \prod k - 1 (1 + \frac{1}{p _{j} - 1})$

Theorem2

$f_{k} (x) = x i = 1 \prod k (1 + \frac{1}{p _{i} - 1})$

Proof

$f_{k} (x) f_{k} (x) - f_{k} (x / p_{i}) = i = 0 \sum k f_{i} (x / p_{i}) = i = 0 \sum k - 1 f_{i} (x / p_{i}) = x i = 0 \sum k - 1 \frac{1}{p _{i}} j = 1 \prod i (1 + \frac{1}{p _{j} - 1}) = x (1 + i = 1 \sum k - 1 \frac{1}{p _{i}} j = 1 \prod i (1 + \frac{1}{p _{j} - 1})) = x i = 1 \prod k - 1 (1 + \frac{1}{p _{i} - 1})$

We can substitute $f_{k} (x) = x \prod_{i = 1}^{k} (1 + \frac{1}{p _{i} - 1})$ , and see the result matches.

$x (1 - \frac{1}{p _{i}}) i = 1 \prod k (1 + \frac{1}{p _{i} - 1}) = x i = 1 \prod k - 1 (1 + \frac{1}{p _{i} - 1})$

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

Theorem3

$f_{k} (x) = O (x lo g k)$

Proof

$f_{k} (x) = x i = 1 \prod k (1 + \frac{1}{p _{i} - 1}) \leq x exp (i = 1 \sum k \frac{1}{p _{i} - 1}) \leq x exp (1 + i = 1 \sum k \frac{1}{p _{i}}) \leq x exp (lo g lo g (k lo g k) + A) = O (x lo g k)$

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

Posted by Chao Xu on 2015-11-20.

Tags: Algorithm.