Space–Time Tradeoffs - Models of Computation: Exploring the Power of Computing - page 502

the Taylor-series expansion of e r , as stated below:
n
r

=

= n

r r r r

n

r r

n r
r !

n !
r !( n

e r

r )! ≤ r ! ≤

−

ρ −s

r− 1 ,where ρ = 2 / ( 2

Later we show that q ( r , s ) ≤ |A| |A| |A|− 1 ) ≤ 2 |A| / 3, from

which it follows that

≤|A| − 1 en
r

2 r

ρ −n ρ r

r

q ( r , s ) N ( r , s ) |A|

r ρ −n en 2 r

≤|A| − 1 2
3

|A|
r

/r ) 2 r since s = n − r . Elementary calculus shows that ( e |A| is an increasing function of

r andthatithasvalue1at r = 0. Since r = 4 / 3, it follows that the

quantity in square brackets is less than 1 for some value of 0 <γ< 1 / 2, which is the
desired conclusion.
We now give a proof by induction that q ( r , s ) satisfies q ( r , s )

γn and ρ ≥

ρ −s

r− 1 . Clearly

≤ |A|

q ( 1, 1 ) ≤ 1 / |A| , since at most one entry in A is zero. This satisfies the bound. We now

assume the inductive hypothesis holds for q ( r − 1, s − 1 ) and q ( r , s − 1 ) and show that it

holds for q ( r , s ) .
Consider an r

× s matrix B .Ithasrank r if the submatrix consisting of the first s −

1

columns has rank r . (This occurs with probability 1

− q ( r , s −

1 ) .) If this is not the case,
there are many other ways in which it can have rank r . In particular, this is true if the
submatrix C consisting of the last r

−

1rowsandthefirst s

−

1 columns of B has rank

r − − q ( r −

1, s

−

1 ) ) and the element b 1, s has an appropriate value

1 (with probability 1

−

1 /

|A|

(with probability at least 1 ), as we now show.

Consider a submatrix D consisting of some r

−

1 linearly independent columns of C .

Consider the r

× r submatrix of B consisting of these same r −

1 columns and its last
column. When the determinant of this matrix is expanded on the first row, the multiplier of
b 1, s is

1 times the determinant of D , which is non-zero. Thus, there is at most one value
for b 1, s that causes the determinant to be zero (the field element causing it to be zero may
not be in the set

±

A |A|−

1 values that cause it to be non-zero. Summarizing this
result, we have the following lower bound:

)oratleast

1 )) 1

1
|A|

− q ( r , s ) ≥ − q ( r , s −

1 )+( 1

− q ( r −

1, s

− −

1 1

1 )) 1

1
|A|

1
|A|

≥ ( 1 − q ( r , s − 1 )) +( 1 − q ( r − 1, s − −

This implies that

1 ) 1

1
|A|

1
|A|

q ( r , s ) ≤ q ( r , s − 1 ) + q ( r − 1, s − −

2

1
|A|

1
|A|

ρ −s + 1

r −

≤ |A|

1

−

ρ −s

r −

1

≤ |A|