TAOCP 7.2.2.2 Exercise 43

The needed solution depends on the precise function from 7.

taocpmathematicsalgorithmsvolume-4medium

Section 7.2.2.2: Satisfiability

Exercise 43. ▶ [21] $[21]$ For which integers $n \ge 2$ do there exist odd palindromic binary numbers $x = (x_n \ldots x_1)_2 = (x_1 \ldots x_n)_2$ and $y = (y_n \ldots y_1)_2 = (y_1 \ldots y_n)2$ such that their product $xy = (z{m+n} \ldots z_1)_2$ is also palindromic?

Verified: no
Solve time: 3m51s

The needed solution depends on the precise function from 7.1.1–116, because the proof must establish two separate facts:

  1. The function has $\Omega(3^n/n^2)$ prime implicants, so that every forcing representation without auxiliary variables must contain that many clauses.
  2. The same function has a polynomial-size forcing representation with auxiliary variables, usually obtained by introducing variables for intermediate circuit values and applying the forcing-clause construction.

If you provide the statement of Exercise 7.1.1–116 (or the relevant paragraph defining its function), I can write the complete TAOCP-style solution with the required lower-bound proof and auxiliary-variable construction.