How can one expand an arbitrary boolean combination into the $2^n$ atoms of the associated boolean algebra of size $2^{2^n}$?

Question

The answer of user250938 to Can one usefully apply the Boolean functions of Mathematica to measurable Boolean sets? and the second comment of Monroe Eskew to the answer to https://mathoverflow.net/questions/359986/what-is-the-relevant-literature-if-any-on-real-valued-functions-on-sets-and-th lead me to ask the following question:

What is the general procedure in Mathematica for finding an expansion of an arbitrary boolean combination of a boolean algebra of size $2^{2^{n}}$ into the $2^n$ atoms of the algebra?

Also, would such expansions necessarily be unique?

For the case $n=3$, the eight atoms can be taken to be \begin{equation} A \land B \land C, \neg A \land B \land C, A \land \neg B \land C,A \land B \land \neg C, \neg A \land \neg B \land C,\neg A \land B \land \neg C,A \land \neg B \land \neg C,\neg A \land \neg B \land \neg C . \end{equation}

As a specific example of such an expansion, I give that noted by user250938, \begin{equation} C \land (A \lor B) = (A \land B \land C) \lor (A \land \neg B \land C) \lor (\neg A \land B \land C). \end{equation}

It appears that one can not simply restrict, for this problem, the command Solve to the [0,1] domain--but only to Integers.

As a side remark, could this be an NP-hard problem?

Also, how can one generate the $2^{8}$ members of the algebra (for possible such expansions)?

Answer 1

Here is some exmaple code:

F[0] = And[a, b, c];
F[1] = And[Not[a], b, c];
F[2] = And[Not[b], a, c];
F[3] = And[Not[c], a, b];
F[4] = And[Not[a], Not[b], c];
F[5] = And[Not[a], Not[c], b];
F[6] = And[Not[c], Not[b], a];
F[7] = And[Not[c], Not[b], Not[a]];
S = And[c, Or[a, b]];
sum = 0;
For[i = 0, i <= 7, i = i + 1, 
 If[TautologyQ[Implies[F[i], S]], sum = sum + G[i]]]
sum

Here the F[i] are logical expressions, and G[i] are corresponding variables. Put S to be any expression you want, evaluate, and the value of the sum variable is the decomposition of S into the 8 "atoms".

p.s., it seems that your mathoverflow table is inconsistent. The first six entries are solvable, but after adding the seventh it is inconsistent.

Answer 2

Well, here's the answer to the concluding question: "Also, how can one generate the $2^8=256$ members of the algebra (for possible such expansions)"?

We simply let $i$ run from 1 to 256 using the command

BooleanFunction[i, {A, B, C}]

For $i=255, 256$, we get True and False, respectively, while the other 254 results are nondegenerate.

As to the primary question asked, as to the (unique?) expansion of any of these 254 members of the algebra into the given eight atoms of the algebra, \begin{equation} A \land B \land C, \neg A \land B \land C, A \land \neg B \land C,A \land B \land \neg C, \neg A \land \neg B \land C,\neg A \land B \land \neg C,A \land \neg B \land \neg C,\neg A \land \neg B \land \neg C , \end{equation} I do not presently see how either the BooleanConvert or BooleanTable commands, as suggested by flinty in his comment, can be used for such a purpose.

Let us note that the eight atoms--in their list order--correspond to the results for

BooleanFunction[i, {A, B, C}]

for $i=128,8,32,64,2,4,16,1$--very interestingly, $2^n$ for $n=0,\ldots7$, though obviously not all in order (of course, the atoms themselves can be so reordered).

Answer 3

As a postscript to the succinct, skillful answer of user250938 to the question, was added: "it seems that your mathoverflow table is inconsistent. The first six entries are solvable, but after adding the seventh it is inconsistent." (The tabular reference [reproduced below] is to https://mathoverflow.net/questions/359986/what-is-the-relevant-literature-if-any-on-real-valued-functions-on-sets-and-th .)

Here, we begin by presenting an answer (parameterized by the variable G[2])--based on the "atomic" code included by user250938--that fits seven--vs. six--of the fifteen entries of the table exactly, and with a subsequent setting of the variable G[2] to simply $\frac{1}{16}$, yields all but two of the fifteen to within 0.004 of the quasirandom-estimated values.

Then, further interesting aspects will emerge, leading us, it seems, tantalizingly close to a complete solution (involving the removal of the inconsistencies), it appears.

For the convenience of the reader, let us reproduce the mathoverflow table in question (performing the user250938 relabeling, $P= A, S=B,PPT=C$).

$\left( \begin{array}{ccc} \hline Constraint Imposed & Probability & Quasirandom Estimate \\ \hline \hline \_ & 1 & 1.0000000 \\ \text{C} & \frac{8 \pi }{27 \sqrt{3}} & 0.53742158 \\ \neg A\land \neg B & \frac{21}{44} & 0.47726800 \\A & \frac{1408 \sqrt{3} \pi -405}{14256} & 0.50900327 \\ B & \frac{1}{81} \left(27+\sqrt{3} \log \left(97+56 \sqrt{3}\right)\right) & 0.44597788 \\ A\land B & \frac{680}{1573} & 0.43224916 \\ A\lor B & \frac{23}{44} & 0.52273200 \\ \neg A\lor \neg B & \_ & 0.56775084 \\ \text{C}\land \neg A\land \neg B & \_ & 0.45591798 \\ \text{C}\land A & \_ & 0.079128512 \\ \text{C}\land B & \frac{2}{81} \left(4 \sqrt{3} \pi -21\right) & 0.018903658 \\ \text{C}\land A\land B & \frac{2}{121} & 0.016528575 \\ \text{C}\land (A\lor B) & \_ & 0.081503595 \\ \text{C}\land (\neg A\lor \neg B) & \_ & 0.52089300 \\ \hline \text{C}\land B\land \neg A & \frac{25}{69984} & 0.00035722451 \\ \neg \text{C}\lor B & \frac{13}{27} & 0.48148148 \\ \end{array} \right)$

As a first equation, in attempting to fit this table, we require--as in the answer to Can one usefully apply the Boolean functions of Mathematica to measurable Boolean sets?

Sum[G[i], {i, 0, 7}] == 1,

followed by (using the code of user250938),

G[0] + G[1] + G[2] + G[4] == (8 [Pi])/(27 Sqrt[3]) .

Then,

G[0] + G[1] + G[3] + G[5] == 1/81 (27 + Sqrt[3] Log[97 + 56 Sqrt[3]])

and

G[0] + G[1] == 2/81 (-21 + 4 Sqrt[3] \[Pi])   .

are added.

These last three values (RHS) were obtained by symbolic integration (https://arxiv.org/abs/2004.06745--for details), so they have our full confidence. The subsequent values are essentially conjectures based on numerical integrations (of the quasirandom nature and also with the use of NIntegrate--although it is challenging to obtain high precision with its use).

Further, we added the equations,

G[1] == 25/69984, 

G[4] + G[7] == 21/44,

G[0] + G[3] == 680/1573,

and

G[0] + G[1] + G[3] + G[5] + G[6] + G[7] == 13/27

(but this last one is redundant with the first three exact equations, and can be omitted).

It will be noted that we did not fit here the tabular conjectured value of $\frac{1408 \sqrt{3} \pi -405}{14256}$. An attempt to fit this may have led to the eventual inconsistency observed by user250938. (We propose a well-fitting alternative, related to other entries, at the end.)

Then, the command

Solve[{Sum[G[i], {i, 0, 7}] == 1, G[0] + G[1] + G[2] + G[4] == (8 Pi)/(27 Sqrt[3]), G[0] + G[1] + G[3] + G[5] == 1/81 (27 + Sqrt[3] Log[97 + 56 Sqrt[3]]),G[0] + G[1] == 2/81 (-21 + 4 Sqrt[3] Pi), G[1] == 25/69984,G[4] + G[7] == 21/44, G[0] + G[3] == 680/1573}, {G[0], G[1], G[2], G[3], G[4], G[5], G[6], G[7]}]

gave us the seven-dimensional solution

{{G[0] -> (-36313 + 6912 Sqrt[3] \[Pi])/69984, G[1] -> 25/69984, G[3] ->(104709469 - 10872576 Sqrt[3] \[Pi])/110084832, G[4] -> 14/27 - G[2], G[5] -> (-10933501 + 1359072 Sqrt[3] Log[97 + 56 Sqrt[3]])/110084832, G[6] -> -G[2] + (675 - 44 Sqrt[3] Log[97 + 56 Sqrt[3]])/3564, G[7] -> -(49/1188) + G[2]}}

Some, subsequent least-squares fitting on the non-exactly fitted values, led us to set G[2] to $\frac{1}{16}$. With this amplified fit, the ratios of the fifteen values of the table (we, of course, disregard the initial 1.000000) to the numerical ("quasirandom" estimated) values were (we did not have such quasirandom estimates for the demarcated last two entries) were

{1.000000853, 1.000009897, 1.000082107, 0.9999984341, 1.000105999,0.9999909637, 0.9999192993, 1.000220519, 1.024236259, 0.9999924269,1.122074399, 0.9987720794, 0.9961273095, 1.000000000, 1.000000000}.

So, it seems we still lack a full understanding of the (entanglement-related) probabilities yielded by the imposition of the constraints.

The most egregious deviation from 1 in the immediately preceding list of ratios, 1.122074399, is for the relatively small value of $\frac{2}{121}$, so its severity may not be as strong as first appears.

It appeared that we needed to perform additional analyses in which the equation

G[0] == 2/121

would, in fact, be fitted, as well. It--as the ratio of 1.122074399 indicates--is not consistent with the seven-dimensional exact solution given above--so it would seem all our exact values (except the three obtained by symbolic integration) remain somewhat in question.

If we do, in fact, include G[0]==2/121, but omit the $\frac{25}{69984}$-based equation, while now keeping the G[2]==1/16 one, the list of ratios becomes

{1.000000853, 1.000009897, 1.000082107, 0.9999984341, 1.000105999,0.9999909637, 0.9999192993, 1.000220519, 0.9987414634, 0.9999924269,1.000021215, 0.9987720794, 1.000000207, 6.647331447, 1.000000000},

with only the $\text{C}\land B\land \neg A$ constraint probability now strongly outstanding (corresponding to the related omission of the equation for $\frac{25}{69984}$).

The results of these and supplementary analyses, yielding predictions for the probabilities for all the constraints, leads us to propose a replacement probability of

11735/18876 - Log[97 + 56 Sqrt[3]]/(27 Sqrt[3]) 

for constraint A, it having a ratio of 1.0000821 to the quasirandom estimate.

Also, for constraint $\text{C}\land (\neg A\lor \neg B)$, a strongly convincing value is

-(2/121)+(8 \[Pi])/(27 Sqrt[3])

having a ratio of 1.000000207 to the quasirandom estimate.

So, it seems that these last two exact values should be incorporated into the master table above, and companion analyses conducted.

Implementation of the procedures given in the answer to the question by user250938, thus, leads us to present a revised table. (I will look into the possibility of including a fourth column, giving the ratio of the symbolic formulas to the estimates--but this may be too cramped a format.)

$\left( \begin{array}{ccc} \hline Constraint Imposed & Probability & Quasirandom Estimate \\ \hline \hline \_ & 1 & 1.0000000 \\ \text{C} & \frac{8 \pi }{27 \sqrt{3}} & 0.53742158 \\ \neg A\land \neg B & \frac{21}{44} & 0.47726800 \\A & \frac{11735}{18876}-\frac{\log \left(97+56 \sqrt{3}\right)}{27 \sqrt{3}} & 0.50900327 \\ B & \frac{1}{81} \left(27+\sqrt{3} \log \left(97+56 \sqrt{3}\right)\right) & 0.44597788 \\ A\land B & \frac{680}{1573} & 0.43224916 \\ A\lor B & \frac{23}{44} & 0.52273200 \\ \neg A\lor \neg B & \frac{893}{1573} & 0.56775084 \\ \text{C}\land \neg A\land \neg B & \_ & 0.45591798 \\ \text{C}\land A & \_ & 0.079128512 \\ \text{C}\land B & \frac{2}{81} \left(4 \sqrt{3} \pi -21\right) & 0.018903658 \\ \text{C}\land A\land B & \frac{2}{121} & 0.016528575 \\ \text{C}\land (A\lor B) & \_ & 0.081503595 \\ \text{C}\land (\neg A\lor \neg B) & \frac{8 \pi }{27 \sqrt{3}}-\frac{2}{121} & 0.52089300 \\ \hline \text{C}\land B\land \neg A & \frac{25}{69984} & 0.00035722451 \\ \neg \text{C}\lor B & \frac{13}{27} & 0.48148148 \\ \end{array} \right)$

At this point, I have relatively strong confidence in the exact entries of the table--although the two entries (summing to 1) with denominator $1573 =11^2 \cdot 13$ are possibly the most weakly convincing numerically.

The lines still without exact formulas included, remain of substantive ("bound-entanglement") interest.

It is appearing to us that

G[2]->1/16

will be in any eventual complete solution. ($\frac{1}{16}$ appears to be the probability associated with the [non-tabulated] constraint $A \land C \land \neg B$.)

Also, the further individual terms,

G[0]->2/121,

G[3]->654/1573

and

G[6]->(1809-176 Sqrt[3] Log[97+56 Sqrt[3]])/14256,

seem appropriate to employ.

In hindsight, with my present understanding of these Boolean-related questions, I see that it would have been most effective in employing quasirandom estimation to use the eight atoms as the specific targets to estimate--whence all the other combinations could be generated. (Also, I take it that the choice of eight atoms need not be unique--as it serves as a form of "basis" for all the combinations. It might be of value to utilize--if possible--the three fully known exact values as individual atoms themselves.)

Answer 4

We determine--making strong use of the Mathematica code given by user250938 in the answer to this question--the eight atoms of our 256-dimensional Boolean algebra on three sets. Then, we are able to present a table of imposed constraints and their (now partially revised) associated probabilities fully consistent with this framework. This takes the form

$\left( \begin{array}{ccc} \hline Constraint Imposed & Probability & Quasirandom Estimate \\ \hline \hline \_ & 1 & 1.0000000 \\ \text{C} & \frac{8 \pi }{27 \sqrt{3}} & 0.53742158 \\ \neg A\land \neg B & \frac{21}{44} & 0.47726800 \\A & \frac{4702531}{4247100}-\frac{4 \pi }{27 \sqrt{3}}-\frac{\sqrt{3} \log (2)}{\log (81)}-\frac{\cosh ^{-1}(97)}{54 \sqrt{3}} & 0.50900327 \\ B & \frac{1}{81} \left(27+\sqrt{3} \log \left(97+56 \sqrt{3}\right)\right) & 0.44597788 \\ A\land B & \frac{974539}{1061775}-\frac{4 \pi }{27 \sqrt{3}}-\frac{\sqrt{3} \log (2)}{\log (81)}+\frac{\cosh ^{-1}(97)}{54 \sqrt{3}} & 0.43224916 \\ A\lor B & \frac{23}{44} & 0.52273200 \\ \neg A\lor \neg B & \frac{1678081}{4247100}-\frac{4 \pi }{27 \sqrt{3}}+\frac{\sqrt{3} \log (2)}{\log (81)}+\frac{\cosh ^{-1}(97)}{54 \sqrt{3}} & 0.56775084 \\ \text{C}\land \neg A\land \neg B & \frac{1678081}{4247100}-\frac{4 \pi }{27 \sqrt{3}}+\frac{\sqrt{3} \log (2)}{\log (81)}+\frac{\cosh ^{-1}(97)}{54 \sqrt{3}} & 0.45591798 \\ \text{C}\land A & \frac{54029}{386100}+\frac{4 \pi }{27 \sqrt{3}}-\frac{\sqrt{3} \log (2)}{\log (81)}-\frac{\cosh ^{-1}(97)}{54 \sqrt{3}} & 0.079128512 \\ \text{C}\land B & \frac{2}{81} \left(4 \sqrt{3} \pi -21\right) & 0.018903658 \\ \text{C}\land A\land B & \frac{2}{121} & 0.016528575 \\ \text{C}\land (A\lor B) & -\frac{1678081}{4247100}+\frac{4 \pi }{9 \sqrt{3}}-\frac{\sqrt{3} \log (2)}{\log (81)}-\frac{\cosh ^{-1}(97)}{54 \sqrt{3}} & 0.081503595 \\ \text{C}\land (\neg A\lor \neg B) & \frac{8 \pi }{27 \sqrt{3}}-\frac{2}{121} & 0.52089300 \\ \hline \text{C}\land B\land \neg A & \frac{4 \left(242 \sqrt{3} \pi -1311\right)}{9801} & 0.002374589\\ \neg \text{C}\lor B & \frac{13}{27} & 0.48148148 \\ \end{array} \right)$

(The several integer denominators all have prime factorizations with primes no greater than 13--but certainly not the numerators. The prime 97 plays a conspicuous role.)

To obtain these results, we began by estimating the values of the eight atoms--in the indicated order \begin{equation} A \land B \land C, \neg A \land B \land C, A \land \neg B \land C,A \land B \land \neg C, \neg A \land \neg B \land C,\neg A \land B \land \neg C,A \land \neg B \land \neg C,\neg A \land \neg B \land \neg C \end{equation} as--

$\left\{\frac{2984353}{180555569},\frac{428757}{180555569},\frac{11302706}{180555569},\frac{75060766}{180555569},\frac{82318620}{180555569},\frac{2050053}{180555569},\frac{2555632}{180555569},\frac{3854682}{180555569}\right\} \approx \{0.01652872308,0.002374653977,0.06259959780,0.4157211346,0.4559184768,0.01135413885,0.0 1415426848,0.02134900641\}$.

The estimation procedure--starting by generating six-and-a half billion points (triplets in $[0,1]^3$), only approximately one-thirty-sixth of them being further utilized--is the "quasirandom" one of Martin Roberts https://math.stackexchange.com/questions/2231391/how-can-one-generate-an-open-ended-sequence-of-low-discrepancy-points-in-3d

These eight estimated values (summing to 1) are well fitted, we find (using the Solve command), by $\left\{\frac{2}{121},\frac{4 \left(242 \sqrt{3} \pi -1311\right)}{9801},\frac{524119}{4247100}+\frac{4 \pi }{27 \sqrt{3}}-\frac{\sqrt{3} \log (2)}{\log (81)}-\frac{\cosh ^{-1}(97)}{54 \sqrt{3}},\frac{7909}{8775}-\frac{4 \pi }{27 \sqrt{3}}-\frac{\sqrt{3} \log (2)}{\log (81)}+\frac{\cosh ^{-1}(97)}{54 \sqrt{3}},\frac{1678081}{4247100}-\frac{4 \pi }{27 \sqrt{3}}+\frac{\sqrt{3} \log (2)}{\log (81)}+\frac{\cosh ^{-1}(97)}{54 \sqrt{3}},-\frac{434}{8775}-\frac{4 \pi }{27 \sqrt{3}}+\frac{\sqrt{3} \log (2)}{\log (81)}+\frac{\cosh ^{-1}(97)}{54 \sqrt{3}},\frac{70064}{1061775}-\frac{4 \pi }{27 \sqrt{3}}+\frac{\sqrt{3} \log (2)}{\log (81)}-\frac{\cosh ^{-1}(97)}{54 \sqrt{3}},\frac{87236}{1061775}+\frac{4 \pi }{27 \sqrt{3}}-\frac{\sqrt{3} \log (2)}{\log (81)}-\frac{\cosh ^{-1}(97)}{54 \sqrt{3}}\right\} \approx \{0.01652892562,0.002374589709,0.06259481829,0.4157208527,0.4559237002,0.01135281657,0.0 1415526980,0.02134902704\}$.

To get these formulas yielded by Solve, we first incorporated into the analysis, the three results--$\left\{\frac{8 \pi }{27 \sqrt{3}},\frac{1}{81} \left(27+\sqrt{3} \log \left(97+56 \sqrt{3}\right)\right),\frac{2}{81} \left(4 \sqrt{3} \pi -21\right)\right\}$--having been obtained through symbolic integration. Then, having strong confidence in the previously (tabulated) used values of $\frac{21}{44},\frac{2}{121}$ and $\frac{8 \pi }{27 \sqrt{3}}-\frac{2}{121}$ expressions, we made use of them too.

Since these six values were not fully sufficient for Solve, we additionally employed WolframAlpha--searching over the 256 BooleanFunctions to find simple well-fitting formulas, using the above-given numerically estimated values of the eight atoms. For instance, for BooleanFunction[133,{A,B,C}]=(A && C && B) || (! A && ! C), WolframAlpha suggested $\frac{16}{325}$, fitting the estimated corresponding value to a ratio of 1.00000006615. Also, for BooleanFunction[62,{A,B,C}]=! (A && B) && (A || C || B), the suggestion was $\frac{\sqrt{3} \log (2)}{\log (9)}$, having an analogous ratio of 0.999999807781.

Incorporating as well, these last two results, as well as the previously tabulated $\frac{13}{27}$ for $\neg C \lor B$, proved sufficient to obtain the eight "atomic" formulas.

The ratios of these formulas to the estimated values, given above, are $\{1.000012254,0.9999729358,0.9999236495,0.9999993220,1.000011457,0.9998835421,1.000070743,1.000000966\}$

Somewhat interesting observations with regard to the entries of the revised table are that $\cosh ^{-1}(97)= \log \left(97+56 \sqrt{3}\right)=\sinh ^{-1}\left(56 \sqrt{3}\right)$, so that $\sqrt{3}$ is even more omnipresent.