Section 7.2.2.2: Satisfiability

Exercise 106. [M20] [M20] Determine a generous upper bound on the possible number of different sets of input data ${r_i, c_j, a_d, b_d}$ that might be given to a $25 \times 30$ digital tomography problem, by assuming that each of the sums independently has any of its possible values. How does this bound compare to $2^{750}$?

Verified: yes
Solve time: 2m16s

---

Solution

For a $25 \times 30$ binary image, each row sum $r_i$ counts the number of $1$s in a row of length $30$, so each $r_i$ has $31$ possible values, namely $0,1,\ldots,30$. The $25$ row sums therefore contribute at most

$31^{25}$

different possibilities.

Each column sum $c_j$ counts the number of $1$s in a column of length $25$, so each $c_j$ has $26$ possible values, namely $0,1,\ldots,25$. The $30$ column sums contribute at most

$26^{30}$

possibilities.

There are $25+30-1=54$ diagonals in each of the two diagonal directions. For one direction, the diagonal lengths are

$1,2,\ldots,24,\underbrace{25,25,25,25,25,25}_{6\text{ times}},24,\ldots,2,1.$

A diagonal of length $k$ has $k+1$ possible sums, from $0$ through $k$. Hence the number of possibilities for all $a_d$ is

$$ \left(\prod_{k=1}^{24}(k+1)\right)^2 26^6

(2\cdot3\cdots25)^2 26^6. $$

The same count applies independently to the $b_d$ sums, giving another factor of

$$ (2\cdot3\cdots25)^2 26^6. $$

Multiplying the independent upper bounds gives the total number of possible input data sets as at most

$$ 31^{25}26^{30} \left((2\cdot3\cdots25)^2 26^6\right)^2. $$

Combining the powers of $26$,

$$ 31^{25}26^{42}(2\cdot3\cdots25)^4. $$

This is the requested generous upper bound.

To compare this with $2^{750}$, take logarithms base $2$:

$$ \log_2\left(31^{25}26^{42}(2\cdot3\cdots25)^4\right)

25\log_2 31+42\log_2 26+4\sum_{k=2}^{25}\log_2 k . $$

Evaluating these terms gives

$$ 25\log_2 31+42\log_2 26+4\sum_{k=2}^{25}\log_2 k \approx 655.999430357. $$

Therefore the bound is approximately

$$ 2^{655.999430357}, $$

which is about $2^{656}$. Since

$$ 656<750, $$

the number of possible tomography data sets is bounded by a quantity much smaller than the number of binary images, $2^{750}$.

The final bound is

$$ \boxed{31^{25}26^{42}(2\cdot3\cdots25)^4\approx 2^{656}}. $$