Algebraic and Combinatorial Circuits - Models of Computation: Exploring the Power of Computing - page 277

Show that the wrapped convolution on n -tuples contains the standard convolution on

( n + 1 ) / 2

-tuples as a subfunction and vice versa.
Hint: In both halves of the problem, it helps to characterize the standard and wrapped
convolutions as matrix-vector products. It is straightforward to show that the wrapped
convolution contains the standard convolution as a subfunction. To show the other re-
sult, observe that the matrix characterizing the standard convolution contains a Toeplitz
matrix as a submatrix. Consider, for example, the standard convolution of two six-
tuples. The matrix associated with the wrapped convolution contains a special type of
Toeplitz matrix.
6.20 Show that the standard convolution function f ( n , n )

conv : R 2 n

R 2 n− 2 is a subfunction →

of the integer multiplication function, f ( n )

mult :

B

2 n log n

→B

2 n log n of Section 2.9

when R is the ring of integers modulo 2.
Hint: Represent the two sequences to be convolved as binary numbers that have been
padded with zeros so that at most one bit in a sequence appears among

log n

posi-

tions.

DISCRETE FOURIER TRANSFORM
6.21 Let n = 2 k . Use proof by induction to show that for all elements a of a commutative
ring

the following identity holds, where is the product operation:
n

R

− k −

1 1

( 1 + a 2 j )

a j =

j = 0 j = 0

6.22 Let n = 2 k and let = 0, let m = ω n/ 2 + 1. R be a commutative ring. For ω ∈R , ω

Show that for 1 ≤ p<n

n −

1

ω pj = 0 mod m

j = 0

Hint: Represent p as the product of the largest power of 2 with an odd integer and
apply the result of Problem 6.21 .
6.23 Let n and ω be positive powers of two. Let m = ω n/ 2 + 1. Show that in the ring ￿ m
of integers modulo m the integer n has a multiplicative inverse and that ω is a principal
n th root of unity.
6.24 Let n be even. Use the results of Problems 6.21 , 6.22 ,and 6.23 to show that ￿ m ,
the set of integers modulo m , m = 2 tn/ 2 + 1 for any positive integer t

≥

2, is a

commutative ring in which ω = 2 t is a principal n th root of unity.
6.25 Let ω be a principal n th root of unity of the commutative ring

R =( R , + , ∗

,0,1 ) .

Show that ω 2 is a principal ( n/ 2 ) th root of unit.
6.26 A circulant is an n

× n matrix in which the r th row is the r th cyclic shift of the first

n .When n is a prime, show that computing the DFT of a vector of
length n is equivalent to multiplying by an ( n

≤ r ≤

row, 2

1 ) circulant.
6.27 Show that the multiplication of circulant matrix with a vector can be done by a circuit
of size O ( n log n ) and depth O (log n ) .

−

1 )

× ( n −