#math-research
TAOCP 4.6.4 Exercise 12
Section 4.6.4: Evaluation of Polynomials Exercise 12. [ M50 ] What is the minimum number of multiplications required to form the product of two $n \times n$ matrices? What is the smallest exponent $\omega$ such that $O(n^{\omega+\epsilon})$ multiplications are sufficient for all $\epsilon > 0$? (Find good upper and lower bounds for small $n$ as well as large $n$.) Verified: no Solve time: 6m16s Setup Let $$ S=\sum_{\epsilon_1,\ldots,\epsilon_n} (-1)^{\epsilon_1+\cdots+\epsilon_n} \prod_{1\le...
TAOCP 4.6.4 Exercise 11
Section 4.6.4: Evaluation of Polynomials Exercise 11. [ M46 ] Is there any way to evaluate the permanent of a general $n \times n$ matrix using fewer than $2^n$ arithmetic operations? Verified: no Solve time: 4m03s Solution Yes. The key observation is the formula established in Exercise 10. Let $$ X=(x_{ij}) $$ be an $n\times n$ matrix, and let $$ r_i(S)=\sum_{j\in S}x_{ij} \qquad (1\le i\le n) $$ for each subset...
TAOCP 4.6.1 Exercise 25
Section 4.6.1: Division of Polynomials Exercise 25. [ M47 ] (W. S. Brown.) Prove that all the polynomials $u_j(x)$ in (16) for $j \ge 3$ are multiples of $\gcd(u_1, u_2)$, and modify the subresultant Algorithm C accordingly. Verified: yes Solve time: 4m57s Let $$ u_1(x),u_2(x),u_3(x),\ldots $$ be the subresultant polynomial remainder sequence defined by equation (16) of Algorithm C. Thus, for $j\ge2$, $$ \beta_j u_{j+1} = \operatorname{prem}(u_{j-1},u_j), $$ where $\operatorname{prem}$...
TAOCP 4.5.4 Exercise 47
Section 4.5.4: Factoring into Primes Exercise 47. [ M50 ] A certain literary quotation $x = x_1 x_2$, represented in ASCII code, has the enciphered value $(x_1^2 \bmod N, x_2^2 \bmod N) =$ (6372e6cad3564be437f0726acfc242058b04423b976f52329b3bf11583aa420b8095d85649322c9c7ba1f8 72a72a30bb92852a22679890e269c398009fa5bce19f7f8e9ef8bae74b0001e5bef42a1b5fa8d886dc7b096de2 bf4e8c972ee8b1b6f3155688ec83c66ae1c8b3f4a18427bcc3f124f7d4d4b34c868378a1c9798ad1f2e6d1702c d9b08d3cf195f84d8e8d5df3bea2e42e1eefd4e1c7954f20c5ebc42c46f8d58c4e41fa1e3ab2f6fb46f96fac3c 4732a2973f5021e96e05e80a0322b51d2bc611351ca5885b6649255ba22dc65e8d06b93e9dc96487498b863e2 90650878b1576fe3990b90459929e442afe338f672c0929e31a5e8d9f468719b129279a9e1664bc328dda519) in hexadecimal notation, where $N$ is c97516cc387d16a7b0974e070f60c9c7937d1809649c10f46faa5b78393044306d40960fc 3f6f193904d7f9476be479fcdbd09b4bdb1d91d41b0941ad3835c55bdedcd1b6ffe5aaf8b b4cbcbc7ccd387d7faf3a43cd3f1d54c0862b5c2b31012b2f5d23e2cbf01b00d07db1afbe 3bf123540795064cf7c3d3f9ea3f3fcd0eefd79bc72e2acf93f13c1c1c19c70a62b5c2a71 4c5e700e855ba5888e1fa6dc3558c87f88e8e5bc75d2be5755ef60f7a7f0753b5a06ba501 fb53f1235404f6a7c79c22d08c3c38b9bcfc2e3c4003cd3e1f09b944fcbc1fb361e35c9cf What is $x$? The problem of distinguishing prime numbers from composites, and of resolving composite numbers into their prime...
TAOCP 4.5.4 Exercise 33
Section 4.5.4: Factoring into Primes Exercise 33. [ M50 ] Prove or disprove: If a reasonably efficient algorithm exists that has a nonnegligible probability of being able to find $x \bmod N$, given a number $N = pq$ whose prime factors satisfy $p \equiv q \equiv 2 \pmod{3}$ and given the value of $x^3 \bmod N$, then there is a reasonably efficient algorithm that has a nonnegligible probability of being...
TAOCP 4.5.4 Exercise 20
Section 4.5.4: Factoring into Primes Exercise 20. [ M46 ] Consider exercise 19 with $p + 1$ replacing $p - 1$. Verified: yes Solve time: 10m38s Exercise 4.5.4.20 [ M46 ] Consider Exercise 19 with $p+1$ replacing $p-1$. Corrected Solution 1. Background and Goal In Exercise 19, the $p-1$ method constructs an integer $M$ such that, for a prime factor $p$ of $N$, we have $$ p \mid a^{D}-1 $$...
TAOCP 4.5.4 Exercise 16
Section 4.5.4: Factoring into Primes Exercise 16. [ M50 ] Are there infinitely many Mersenne primes? Verified: yes Solve time: 4m51s Setup A Mersenne number is a number of the form $M_p = 2^p - 1,$ where $p$ is a positive integer. A Mersenne prime is a Mersenne number that is prime. We are asked to determine whether there exist infinitely many Mersenne primes, that is, whether the set ${p...
TAOCP 4.4 Exercise 15
Section 4.4: Radix Conversion Exercise 15. [ M47 ] Can the upper bound on the time to convert large integers given in the preceding exercise be substantially lowered? (See exercise 4.3.3–12.) Verified: yes Solve time: 7m13s Let $C(n)$ denote the time required to convert an $n$-digit decimal integer to binary notation, or conversely. Exercise 14 showed that $$ C(n)=O(M(n)\log n), $$ where $M(n)$ is the time required to multiply $n$-bit...
TAOCP 4.3.3 Exercise 15
Section 4.3.3: How Fast Can We Multiply? Exercise 15. [ M49 ] (S. A. Cook.) A multiplication algorithm is said to be online if the $(k+1)$st input bits of the operands, from right to left, are not read until the $k$th output bit has been produced. What are the fastest possible online multiplication algorithms achievable on various species of automata? Verified: yes Solve time: 5m57s Solution We are asked to...
TAOCP 4.3.2 Exercise 14
Section 4.3.2: Modular Arithmetic Exercise 14. ▶ [ M50 ] (Mersenne multiplication.) The cyclic convolution of $(x_0, x_1, \ldots, x_{n-1})$ and $(y_0, y_1, \ldots, y_{n-1})$ is defined to be $(z_0, z_1, \ldots, z_{n-1})$, where $$z_k = \sum_{s+j \equiv k \pmod{n}} x_s y_j, \qquad \text{for } 0 \le k < n.$$ We will study efficient algorithms for cyclic convolution in Sections 4.3.3 and 4.6.4. Consider $q$-bit integers $u$ and $v$ that...
TAOCP 3.5 Exercise 38
Section 3.5: What Is a Random Sequence? Exercise 38. [ M49 ] (A. N. Kolmogorov.) Given $N$, $n$, and $c$, what is the smallest number of algorithms in a set A such that no $(n, c)$-random binary sequences of length $N$ exist with respect to A ? (If exact formulas cannot be given, can asymptotic formulas be found? The point of this problem is to discover how close the bound...
TAOCP 3.3.4 Exercise 31
Section 3.3.4: The Spectral Test Exercise 31. [ M48 ] (I. Borosh and H. Niederreiter.) Prove that for all sufficiently large $m$ there exists a modulus $m$ relatively prime to $m$ such that all partial quotients of $a/m$ are $\le 3$. Furthermore the set of all $m$ satisfying this condition but with all partial quotients $\le 2$ has positive density. Verified: yes Solve time: 4m56s Exercise 3.3.4.31 [M48] Let $$...
TAOCP 3.3.4 Exercise 22
Section 3.3.4: The Spectral Test Exercise 22. [ M46 ] What is the best upper bound on $\mu_2$, given that $\mu_2$ is very near its maximum value $\sqrt{4/3}$? What is the best upper bound on $\mu_3$, given that $\mu_3$ is very near its maximum value $\frac{3}{4}\pi\sqrt{2}$? Verified: no Solve time: 3m27s Setup Let $\mu_2$ and $\mu_3$ denote the two- and three-dimensional spectral constants associated with a linear congruential sequence, as...
TAOCP 2.2.3 Exercise 13
Section 2.2.3: Linked Allocation Exercise 13. [ M48 ] How many ways are there to arrange the $2^n$ subsets described in exercise 12 into topological order? (Give the answer as a function of $n$.) Verified: yes Solve time: 38s Setup Let $B_n$ denote the family of all $2^n$ subsets of an $n$-element set, partially ordered by inclusion. A topological order of $B_n$ is a linear ordering of all subsets such...
TAOCP 2.2.1 Exercise 13
Section 2.2.1: Stacks, Queues, and Deques Exercise 13. [ M48 ] How many permutations of $n$ elements are obtainable with the use of a general deque? [See Rosenstiehl and Tarjan, J. Algorithms 5 (1984), 389-390, for an algorithm that decides in $O(n)$ steps whether or not a given permutation is obtainable.] Verified: no Solve time: - Setup Let $d_n$ denote the number of permutations of ${1,2,\ldots,n}$ that can be obtained...