{\huge One Man's Floor Is Another Man's Ceiling}

Factoring again, always factoring... \vspace{.5in}

Peter Borwein is among those who carry forward the title task of Alan Turing's famous paper, ``On Computable Numbers...'' With David Bailey and Simon Plouffe, he found a new kind of fast formula for computing individual digits of $latex {\pi}&fg=000000$ without having to calculate all preceding ones, as we covered here and here. His brother Jonathan Borwein is likewise among the ``fathers'' of experimental mathematics as a discipline. Peter is currently the Founding Director of the IRMACS Centre at Simon Fraser University.

Today we discuss a recent paper with his co-author Joe Hobart on the power of division.

There are other talented pairs of brothers in mathematics and computer science theory. The Lenstras---Jan, Hendrik, Arjen, and Andries---account for six pairs all by themselves. I (Dick) have been a colleague of Michael Fischer, whose late brother Patrick is being honored with a symposium this coming November 5th at the University of Michigan. The Chudnovsky brothers, Gregory and David, also do experimental mathematics. Gregory Chudnovsky won a MacArthur ``genius grant'' in 1981, and this reminds us to congratulate graph theorist Maria Chudnovsky (alongside Daniel Spielman) on her just-announced MacArthur award, but she is not related. My colleague Dana Randall is the sister of physicist Lisa Randall, but I don't know any comparable sister combinations in theory.

The paper by Borwein and Hobart is in the August/September issue of the American Mathematical Monthly, and is titled ``The Extraordinary Power Of Division in Straight Line Programs.''

The point of this note is to advertise [a] lovely circle of ideas..that if it is possible to divide quickly, then it is possible to factor quickly.

Releasing the power of division, however, requires teaming it with the humble floor function.

The Floor Function

Ken and I both remember courses in high school and/or college in which the integer floor of a real number $latex {x}&fg=000000$ was written $latex {[x]}&fg=000000$. This notation goes back, of course, to Carl Friedrich Gauss. But it wasn't named for Gauss, and perhaps that made it liable to replacement by someone with a better idea. Kenneth Iverson split Gauss' brackets by introducing separate floor and ceiling functions:

$latex \displaystyle \lfloor\pi\rfloor = 3;\quad \lceil\pi\rceil = 4.&fg=000000$

He introduced those symbols into his programming language APL, and the worth of good notation proved out in their now-universal adoption. To quote the singer-songwriter Paul Simon:

There's been some hard feelings here About some words that were said Been some hard feelings here And what is more There's been a bloody purple nose And some bloody purple clothes That were messing up the lobby floor It's just apartment house rules So all you 'partment house fools Remember: one man's ceiling Is another man's floor One man's ceiling Is another man's floor.

A Smale Problem

In 1998 Steven Smale published his list of great problems for the next century---this century. After leading off with the Riemann Hypothesis, Poincaré Conjecture, and P vs. NP, he stated

Problem 4: Integer zeros of a polynomial of one variable.

Given a polynomial $latex {f(x)}&fg=000000$ with integer coefficients, define $latex {\tau(f)}&fg=000000$ to be the number of steps needed to create a formula for $latex {f}&fg=000000$ starting with $latex {1}&fg=000000$ and $latex {x}&fg=000000$, where each step is addition, subtraction, or multiplication of two previously-created formulas. A sequence of such steps is called a straight-line program for $latex {f}&fg=000000$. Let $latex {Z(f)}&fg=000000$ be the number of zeroes of $latex {f}&fg=000000$ that are integers---could be none, could be many. The problem is simple:

Is there a fixed $latex {\epsilon > 0}&fg=000000$ such that for all $latex {f}&fg=000000$, $latex {\tau(f) = \Omega(Z(f)^{\epsilon})}&fg=000000$?

If $latex {f}&fg=000000$ has no integer zeroes this says nothing, but if $latex {f}&fg=000000$ has many integer zeroes, then this says $latex {f}&fg=000000$ is hard to compute. An example of such an $latex {f}&fg=000000$ is the factorial polynomial,

$latex \displaystyle f(x) = (x-1)(x-2)(x-3)\cdots(x-N).&fg=000000$

Is there a constant $latex {c > 0}&fg=000000$ such that for all $latex {N}&fg=000000$, $latex {\tau(N!) \leq n^c}&fg=000000$?

Or---stronger than ``no''---is there an $latex {\epsilon > 0}&fg=000000$ such that $latex {\tau(N!) > n^{\epsilon}}&fg=000000$? Here $latex {\tau(k)}&fg=000000$ for an integer $latex {k}&fg=000000$ means the number of steps required by a straight-line program that starts with just $latex {1}&fg=000000$, no variables. With Michael Shub, Smale showed that if there is no sequence $latex {i_N}&fg=000000$ of integers that ``help'' in the sense of $latex {\tau(i_N N!) \leq n^c}&fg=000000$, then the problem analogous to $latex {\mathsf{SAT}}&fg=000000$ in their model with Lenore Blum of computation over $latex {\mathbb{C}}&fg=000000$ is intractable, giving a $latex {\mathsf{P \neq NP}}&fg=000000$-style consequence for that model.

Information Overload and Extraction

In one sense the algebraic models are really weak, and in another they are super powerful. They do not allow you to treat numbers as strings of bits, so as to encode arbitrary Boolean functions in them. They do not give you arbitrary coefficients on the polynomials $latex {f(x)}&fg=000000$, but only ones you can build up from $latex {1}&fg=000000$ by $latex {+,-,*}&fg=000000$, which is why even computing integers is a challenge.

However, they allow storing values with unlimited precision, and repeated squaring can create some huge values. If we square a $latex {k}&fg=000000$-digit number $latex {r}&fg=000000$, and do it $latex {n}&fg=000000$ times, then we have the number $latex {R = r^{2^n}}&fg=000000$ which has $latex {k2^n}&fg=000000$ digits. There is no way a ``real'' $latex {\mathsf{poly(n)}}&fg=000000$-time program can enumerate all those digits, although a straight-line program is allowed to pretend it has them. The question is, how may we access them?

We have often on this blog considered exponential-size structures that are succinct, meaning there is a polynomial-size object that allows extracting any specified entry $latex {j}&fg=000000$ of the structure. For instance, the structure can be a long string or number and the object can be a small circuit $latex {C}&fg=000000$ such that for all $latex {j}&fg=000000$, $latex {C(j)}&fg=000000$ returns the $latex {j}&fg=000000$th bit. We could modify this idea to create a circuit $latex {C(i,j)}&fg=000000$ returning the bits between $latex {i}&fg=000000$ and $latex {j}&fg=000000$, provided $latex {j - i = \mathsf{poly}(n)}&fg=000000$. (We index the least significant bit by $latex {0}&fg=000000$.)

We do not know whether short straight-line programs preserve succinctness. Besides the connection to factoring, this could even be related to issues about the complexity of integer multiplication that we raised here. But division and the floor function do the same job nicely. Namely, to get the bits of a big number $latex {R}&fg=000000$ in the $latex {2^i}&fg=000000$ place through the $latex {2^j}&fg=000000$ place, which we denote by $latex {r = R[i...j]}&fg=000000$, compute:

$latex \displaystyle \begin{array}{rcl} \ell &=& \lfloor R/2^i\rfloor\\ r &=& \ell - \lfloor\ell/2^{j+1}\rfloor*2^{j+1}. \end{array} &fg=000000$

The mod trick here is general: to compute $latex {R}&fg=000000$ mod $latex {N}&fg=000000$ do $latex {R - \lfloor{R/N}\rfloor*N}&fg=000000$.

Factoring Via Factorials

The next trick noted by Borwein and Hobart is to compute a binomial coefficient by powering and bit-extraction..

Theorem 1 In standard binary notation,

$latex \displaystyle R' = \binom{m}{k} = R[mk+1...mk+1+m]\quad\text{where}\quad R = (1 + 2^m)^m.&fg=000000$

What happens is that the products of $latex {10000\dots 0001}&fg=000000$ align the $latex {1}&fg=000000$'s in columns so that their sums give each binomial coefficient, and the offset of $latex {mk+1}&fg=000000$ from the right locates the sum for $latex {\binom{m}{k}}&fg=000000$. Even if $latex {m}&fg=000000$ is a big number like $latex {2^n}&fg=000000$, this can be done in $latex {\mathsf{poly}(n)}&fg=000000$ steps by repeated squaring.

In fact, raising to the $latex {m}&fg=000000$-th power when $latex {m}&fg=000000$ is not a power of $latex {2}&fg=000000$ involves the problem of finding an efficient straight-line program to compute $latex {m}&fg=000000$ itself. But in any event, when $latex {m}&fg=000000$ is exponential in the complexity parameter $latex {n}&fg=000000$, the process is no worse than polynomial in $latex {n}&fg=000000$, even though the theorem creates a number with about $latex {m^2}&fg=000000$ digits. The range $latex {R'}&fg=000000$ of $latex {m}&fg=000000$ bits extracted---usually with some leading $latex {0}&fg=000000$s---still has exponential size, however.

If we can manipulate $latex {R'}&fg=000000$, however, then we can factor. The trick is the following:

Theorem 2 If $latex {m}&fg=000000$ is even, $latex {m = 2k}&fg=000000$, then $latex {m! = \binom{m}{k}(k!)^2}&fg=000000$.

By recursing from $latex {m}&fg=000000$ to $latex {m/2}&fg=000000$, or when $latex {m}&fg=000000$ is odd, doing $latex {m! = m(m-1)!}&fg=000000$ and recursing from $latex {m-1}&fg=000000$ to $latex {(m-1)/2}&fg=000000$, we can write a standard straight-line program that computes $latex {m!}&fg=000000$ in time $latex {O(nt)}&fg=000000$, where $latex {n = O(\log m)}&fg=000000$ and $latex {t}&fg=000000$ is the time to compute $latex {\binom{m}{m/2}}&fg=000000$. If $latex {t = \mathsf{poly(n)}}&fg=000000$, as above when division and floor are allowed to extract bits, then $latex {m!}&fg=000000$ has a $latex {\mathsf{poly}(n)}&fg=000000$-sized straight-line program.

Finally, to factor an $latex {n}&fg=000000$-bit Blum integer of the form $latex {N = pq}&fg=000000$ with primes $latex {p < q}&fg=000000$, we can use Newton's method to compute $latex {m}&fg=000000$ close enough to $latex {\sqrt{N}}&fg=000000$ to assure $latex {p \leq m < q}&fg=000000$, so that $latex {\text{\it gcd}(m!,N) = p}&fg=000000$. In the absence of a direct comparison for $latex {2^n}&fg=000000$-bit numbers like $latex {m!}&fg=000000$, Euclid's algorithm can still be implemented using division and floor, as shown in the paper. The result is a $latex {\mathsf{poly}(n)}&fg=000000$-sized straight-line program that does factoring.

Wiz or Swiz?

I am stopping in England on my way to Doha, and Ken gave me some prep about the natives. The British have a word ``swiz'' which means something that doesn't turn out as advertised. Division and floor are easy functions, so saying that allowing them in programs means we can factor means we can factor, no? The ``swindle'' is that $latex {m!}&fg=000000$ and $latex {\binom{m}{m/2}}&fg=000000$ are exponential-sized numbers, which the straight-line programs are not being fairly charged for.

Still, we may not need to compute all of these numbers. Right off the bat, we only need $latex {\text{\it gcd}(m!\text{~mod~}N,N)}&fg=000000$ to get $latex {p}&fg=000000$, and can try to reduce mod $latex {N}&fg=000000$ while computing $latex {m!}&fg=000000$, We have blogged recently about cases where a ``lazy'' approach can be more efficient. Perhaps a breakthrough in the ``easy'' problem of integer multiplication can find new regularities in powering that help. If the straight-line model used by Shub and Smale can simulate integer division, even just for restricted cases, all these factors come into play.

Open Problems

Borwein and Hobart themselves ask,

Given a straight line program for $latex {n}&fg=000000$ (...), is it possible to find a nontrivial factorization of $latex {n}&fg=000000$ just given the information in the program?

The paper gives other open problems, of which the last is whether the known polynomial-time algorithms for factoring polynomials can be implemented by comparably efficient straight-line programs.