Introduction
In holographic theories the entropy of a boundary region is computed by the area of an extremal surface in the bulk, by the formula of Ryu and Takayanagi and its covariant extension [1 , 2 ] . Beyond subadditivity and strong subadditivity [3 ] , these entropies obey further linear inequalities, the first found being the monogamy of mutual information (MMI) [4 ] , which also holds for the covariant formula under the assumptions of [5 ] . For N N N A A A B B B C C C … \ldots … O O O H E C N ⊂ R 2 N − 1 \mathrm{HEC}_N \subset\mathbb{R}^{2^N-1} HEC N ⊂ R 2 N − 1 H E C N \mathrm{HEC}_N HEC N [6 ] . The cone is known completely for N ≤ 5 N \le5 N ≤ 5 [6 , 7 ] , and two infinite families of its facets are known [8 , 9 ] .
The main method for proving that a candidate inequality ∑ l α l S ( I l ) ≥ ∑ r β r S ( J r ) \sum_l \alpha_l S(I_l) \ge\sum_r \beta_r S(J_r) ∑ l α l S ( I l ) ≥ ∑ r β r S ( J r ) [6 ] . Each party has an occurrence word on each side, which records the terms that contain it. A contraction map sends the Boolean cube of the left-hand side to that of the right-hand side, maps occurrence words to occurrence words and does not increase weighted Hamming distances. Bao et al. showed that such a map proves the inequality, and proved the five-party facets in this way [6 , 7 ] . The list of five-party facets was shown to be complete in [7 ] . Much work since has gone into understanding and constructing contraction maps [10 , 11 , 12 , 13 , 14 , 15 , 16 , 17 ] ; see also [18 ] .
Whether a valid inequality has a contraction proof depends on how it is presented. A coefficient can be kept as a weight or split into unit copies of its term, on either side, and the whole inequality can be multiplied by a positive integer k k k [6 , 19 , 16 ] . Bao, Furuya and Naskar claim that every valid holographic entropy inequality with rational coefficients has a contraction map, and in the arXiv version of their paper of 14 July 2026 they specify that a map may be sought for any presentation obtained by merging or expanding terms and by uniformly rescaling all coefficients [20 ] . The claim also appears, without that specification, in the PhD thesis of Naskar of 15 June 2026 [21 ] . Several recent works assume that the inequalities they study have contraction proofs [22 , 23 ] . Grimaldi, Headrick, Hubeny and Shteyner remark that, empirically, when the fully split presentation of an inequality has no map, multiplying the inequality by an integer does not create one; their discussion concerns primitive, that is facet-defining, inequalities [16 ] . Whether the scaling is ever needed, and for which inequalities, is the subject of this paper.
An inequality is balanced if every party has the same total coefficient on both sides [6 ] , and superbalanced if, in addition, every inequality obtained from it by exchanging a party with the purifier is balanced, a notion introduced in [24 ] and put in this form in [25 ] . He, Hubeny and Rangamani proved that every facet of H E C N \mathrm{HEC}_N HEC N [25 ] . For the facets at small N N N N ≤ 4 N \le4 N ≤ 4 H E C N \mathrm{HEC}_N HEC N [6 ] , and these have unscaled maps. Of the eight orbits of facets of H E C 5 \mathrm{HEC}_5 HEC 5 [7 ] , our computer search found an unscaled map on the full cube for a representative of each. These maps are not among our certificates, and nothing below uses them. This raises three questions. Does every valid balanced, or superbalanced, inequality have an unscaled contraction proof? If not, how large must the scaling be? And what happens at the facets?
We answer the first question in the negative for both classes, give partial answers to the second, and follow one failure to a facet. A map for an inequality Q Q Q Ω ⊆ { 0 , 1 } L \Omega\subseteq\{0,1\}^{L} Ω ⊆ { 0 , 1 } L Definition 2.6 , that is, a contraction map of Bao et al. for the presentation with merged left-hand side and split right-hand side, which on the full cube is the most permissive unscaled presentation (§ 2.3 ). The domain is either the full cube or the realizable domain A ( Q ) \mathcal{A}(Q) A ( Q ) Definition 2.11 , and k min A ( Q ) k_{\min}^{A}(Q) k m i n A ( Q ) k min Λ ( Q ) k_{\min}^{\Lambda}(Q) k m i n Λ ( Q ) k k k k Q kQ k Q Definition 2.10 ). In this paper we give a proof of the following statement.
Theorem 1.1.
(a) The seven-party inequality B 7 ∗ B_7^* B 7 ∗ (10) is balanced and valid. It has no map on the full cube and none on its realizable domain, and 2 B 7 ∗ 2B_7^* 2 B 7 ∗ k min ( B 7 ∗ ) = k min A ( B 7 ∗ ) = 2 k_{\min}(B_7^*) = k_{\min}^{A}(B_7^*) = 2 k m i n ( B 7 ∗ ) = k m i n A ( B 7 ∗ ) = 2
(b) The six-party inequality U 6 U_6 U 6 (13) is superbalanced and valid. It has no map on the full cube and none on its realizable domain, and 2 U 6 2U_6 2 U 6 k min A ( U 6 ) = 2 k_{\min}^{A}(U_6) = 2 k m i n A ( U 6 ) = 2 Q 8 Q_8 Q 8 (18) and the seven-party inequalities E 0 , … , E 5 E_0,\ldots,E_5 E 0 , … , E 5 § 4 , where E 0 E_0 E 0 3 Q 8 3Q_8 3 Q 8 E s + 1 E_{s+1} E s + 1 E s E_s E s
(c) The seven-party superbalanced inequality F 7 F_7 F 7 (22) defines a facet of H E C 7 \mathrm{HEC}_7 HEC 7 H E C 7 \mathrm{HEC}_7 HEC 7 E 0 E_0 E 0 F 7 F_7 F 7 Stab ( F 7 ) ≅ S 3 \operatorname{Stab}(F_7) \cong\mathcal{S}_3 Stab ( F 7 ) ≅ S 3 F 7 F_7 F 7 § 8 .§ 4 ).
(d) The inequality 3 Q 8 3Q_8 3 Q 8 2 E 0 2E_0 2 E 0 2 E 1 2E_1 2 E 1 2 E 3 2E_3 2 E 3 2 E 4 2E_4 2 E 4 k min ( E s ) = k min A ( E s ) = 2 k_{\min}(E_s) = k_{\min}^{A}(E_s) = 2 k m i n ( E s ) = k m i n A ( E s ) = 2 s = 0 , 1 , 3 , 4 s = 0,1,3,4 s = 0 , 1 , 3 , 4
every j ≥ 0 j \ge0 j ≥ 0 D j D_j D j § 6.3 , on N = 4 j + 7 N = 4j + 7 N = 4 j + 7 k min ( D j ) = 2 j + 2 = 2 ( N + 1 ) / 4 k_{\min}(D_j) = 2^{j+2} = 2^{(N+1)/4} k m i n ( D j ) = 2 j + 2 = 2 ( N + 1 ) /4 Z 7 Z_7 Z 7 (37) has k min ( Z 7 ) = 8 k_{\min}(Z_7) = 8 k m i n ( Z 7 ) = 8 N ≥ 3 N \ge3 N ≥ 3 N N N Q N Q_N Q N k min ( Q N ) < ∞ k_{\min}(Q_N) < \infty k m i n ( Q N ) < ∞ log 2 k min ( Q N ) ≥ 5 4 log 2 N − ( 5 4 + ϵ N ) N \log_2 k_{\min}(Q_N) \ge\frac{5}{4}\log_2 N - \left(\frac{5}{4} + \epsilon_N\right)N log 2 k m i n ( Q N ) ≥ 4 5 log 2 N − ( 4 5 + ϵ N ) N ϵ N → 0 \epsilon_N \to0 ϵ N → 0 N → ∞ N \to\infty N → ∞ N N N Q Q Q k min ( Q ) < ∞ k_{\min}(Q) < \infty k m i n ( Q ) < ∞ k min ( Q ) ≤ 2 ( N + 1 ) ( N + 1 ) / 2 2 − N < N N / 2 k_{\min}(Q) \le2(N+1)^{(N+1)/2}2^{-N} < N^{N/2} k m i n ( Q ) ≤ 2 ( N + 1 ) ( N + 1 ) /2 2 − N < N N /2
Part (a) shows that balance does not guarantee an unscaled contraction proof. The failure is visible at a single point of the cube, where an integer map would need three edges of two disjoint triangles of parties that together touch all six vertices (§ 3 ). Part (b) shows that superbalance does not guarantee one either, already for six parties. The six-party inequality U 6 U_6 U 6 § 4.1 ), and for the eight- and seven-party inequalities the failure persists when sums of instances of MMI, which have unscaled maps, are subtracted in five steps. For E 0 E_0 E 0 E 1 E_1 E 1 E 3 E_3 E 3 E 4 E_4 E 4 N N N § 6.5 ), and for them the least scaling, when finite, is below N N / 2 N^{N/2} N N /2 [20 ] , and they show that the uniform rescaling allowed there cannot be dropped.
Each statement has one of three statuses. It is certified if it rests on an explicit certificate, a DRAT proof, an exact map, a list of graph models or an exact identity, checked by a program independent of the one that produced it (Appendix § 8 ). A DRAT proof on a subdomain to which every map on a larger domain restricts, such as the subdomain U ( Q ) \mathcal{U}(Q) U ( Q ) Lemma 2.15 , counts as a certificate on that larger domain. It is derived if it follows from certified statements by a short proof given in the text, and argued if it rests on a written proof that was checked only by other instances of the models that wrote it, as described below. In Theorem 1.1 , the statements that a map exists or does not exist are certified in parts (a)–(c) and, in part (d), for 3 Q 8 3Q_8 3 Q 8 2 E 0 2E_0 2 E 0 2 E 1 2E_1 2 E 1 2 E 3 2E_3 2 E 3 2 E 4 2E_4 2 E 4 Z 7 Z_7 Z 7 B 7 ∗ B_7^* B 7 ∗ Proposition 3.2 (iii) and is argued. For U 6 U_6 U 6 Proposition 4.3 (iii) gives in addition a written proof. For the family D j D_j D j D 0 D_0 D 0 D 1 D_1 D 1 Table 3 . All results on star inequalities for general N N N Theorems 6.10 , 6.14 and 6.17 , Corollary 6.22 and Proposition 6.24 , are argued, with proofs in Appendix B, and the lower bound of part (d) rests in addition on a theorem of Alon and Vũ [26 ] . Validity is certified for B 7 ∗ B_7^* B 7 ∗ U 6 U_6 U 6 Q 8 Q_8 Q 8 E 0 E_0 E 0 E 1 E_1 E 1 E 3 E_3 E 3 E 4 E_4 E 4 E 2 E_2 E 2 E 5 E_5 E 5 E 7 E_7 E 7 Lemma 2.13 . The facet statement and the containment of faces in part (c) are derived (Theorem 5.2 , Proposition 5.4 ).
Use of large language models and status of the proofs
This paper was produced by large language models, instances of the Claude models of Anthropic running as autonomous agents, in October and November 2026. They found the inequalities, wrote the proofs and the programs of Appendix § 8 , ran the computations and wrote the text. The arguments were checked only by other instances of the same models, acting as referees and recomputing the certificates with programs of their own. Such checks may share the blind spots of the models that wrote the proofs. The author has read the paper and checked that the references lead to the cited works, but the statements attributed to them were checked only by the models: each statement was matched to a verbatim passage of the cited work, and another instance of the model ruled on whether the passage supports the sentence. No human expert has checked the proofs. The steps we regard as least secure are the SAT encodings and the argued results on star inequalities of § 6.2 –§ 6.4 . A DRAT proof certifies only that a formula is unsatisfiable, while the step from the map problem to the formula rests on the encoder (a single one for E 5 E_5 E 5 3 Q 8 3Q_8 3 Q 8 V 7 V_7 V 7 § 5 ). The validity of E 2 E_2 E 2 E 5 E_5 E 5 F 7 F_7 F 7 Lemma 2.13 , which for our rational certificates reduces to a theorem of Avis and Hernández-Cuenca (§ 2.4 ).
Code availability
The programs that check the certificates of Appendix § 8 , the certificates themselves, and a program that regenerates the Boolean formulas and the integer maps are available under the MIT license at https://github.com/ahippelainen/unscaled-contraction-public.
Conventions
Parties are A , B , C , … A, B, C, \ldots A , B , C , … O O O [ N ] = { 1 , … , N } [N] = \{1, \ldots, N\} [ N ] = { 1 , … , N } A B C ABC A B C S ( A B C ) S(ABC) S ( A B C ) 2 A B C 2ABC 2 A B C 2 S ( A B C ) 2S(ABC) 2 S ( A B C ) O O O Q ∈ Z 2 N − 1 Q \in\mathbb{Z}^{2^N-1} Q ∈ Z 2 N − 1 Q ⋅ S ≥ 0 Q \cdot S \ge0 Q ⋅ S ≥ 0 k Q kQ k Q k k k MMI ( X : Y : Z ) \operatorname{MMI}(X:Y:Z) MMI ( X : Y : Z ) S ( X Y ) + S ( X Z ) + S ( Y Z ) ≥ S ( X ) + S ( Y ) + S ( Z ) + S ( X Y Z ) S(XY) + S(XZ) + S(YZ) \ge S(X) + S(Y) + S(Z) + S(XYZ) S ( X Y ) + S ( X Z ) + S ( Y Z ) ≥ S ( X ) + S ( Y ) + S ( Z ) + S ( X Y Z ) MMI ( B C : D E : F G ) \operatorname{MMI}(BC:DE:FG) MMI ( B C : D E : F G ) X = { B , C } X = \{B,C\} X = { B , C } [ P ] [P] [ P ] P P P o ( 1 ) o(1) o ( 1 ) N N N N → ∞ N \to\infty N → ∞ k ≥ N ( c − o ( 1 ) ) N k \ge N^{(c-o(1))N} k ≥ N ( c − o ( 1 )) N ε > 0 \varepsilon> 0 ε > 0 k ≥ N ( c − ε ) N k \ge N^{(c-\varepsilon)N} k ≥ N ( c − ε ) N N N N k ≤ N ( c + o ( 1 ) ) N k \le N^{(c+o(1))N} k ≤ N ( c + o ( 1 )) N k ≤ N ( c + ε ) N k \le N^{(c+\varepsilon)N} k ≤ N ( c + ε ) N N N N
The method
All our statements about contraction proofs concern integer maps n = ( n r ) r = 1 R : Ω → ∏ r { 0 , 1 , … , β r } n = (n_r)_{r=1}^{R}:\Omega\to\prod_r\{0,1,\ldots,\beta_r\} n = ( n r ) r = 1 R : Ω → ∏ r { 0 , 1 , … , β r } Ω ⊆ { 0 , 1 } L \Omega\subseteq\{0,1\}^{L} Ω ⊆ { 0 , 1 } L
n r ( x ( i ) ) = β r [ i ∈ J r ] ( i ∈ [ N ] ) , n ( 0 ) = 0 , ∑ r = 1 R ∣ n r ( u ) − n r ( v ) ∣ ≤ d α ( u , v ) ( u , v ∈ Ω ) . (1) n_r\left(x^{(i)}\right)=\beta_r[i\in J_r]\quad(i\in[N]),\qquad n(0)=0,\qquad\sum_{r=1}^{R}\left|n_r(u)-n_r(v)\right|\le d_\alpha(u,v)\quad(u,v\in\Omega). \tag*{(1)} n r ( x ( i ) ) = β r [ i ∈ J r ] ( i ∈ [ N ]) , n ( 0 ) = 0 , r = 1 ∑ R ∣ n r ( u ) − n r ( v ) ∣ ≤ d α ( u , v ) ( u , v ∈ Ω ) . (1) where x ( i ) ∈ { 0 , 1 } L x^{(i)} \in\{0,1\}^{L} x ( i ) ∈ { 0 , 1 } L i i i d α d_\alpha d α n r ( u ) n_r(u) n r ( u ) β r \beta_r β r S ( J r ) S(J_r) S ( J r ) u u u [27 ] , machine-checkable proofs that a Boolean formula is unsatisfiable, for SAT encodings of the map problem (Appendix § 8 .§ 1 ) on the full cube or on a small subdomain U ( Q ) U(Q) U ( Q ) A ( Q ) A(Q) A ( Q ) Lemma 2.15 ). Validity is certified by exact identities with instances of subadditivity and MMI or by exact rational real maps on the full cube or on A ( Q ) A(Q) A ( Q ) Lemma 2.13 : a real map on A ( Q ) A(Q) A ( Q ) Q Q Q 2 N − 2 2^N-2 2 N − 2 Π ( Q ) \Pi(Q) Π ( Q ) k Q kQ k Q Π ( Q ) \Pi(Q) Π ( Q ) 1 k Z m \frac{1}{k}\mathbb{Z}^{m} k 1 Z m Theorem 6.10 ). Balance conditions of coin weighing make Π ( Q ) \Pi(Q) Π ( Q ) Theorem 6.14 ), and the ill-conditioned weighing matrices of Alon and Vũ [26 ] make this weight superexponentially large (Corollary 6.22 ). The upper bound comes from Cramer's rule and Hadamard's inequality at a vertex of Π ( Q ) \Pi(Q) Π ( Q ) Proposition 6.24 ).
Section 2 defines contraction maps in count form and the realizable domain and proves two lemmas that are used throughout the paper. Sections 3, 4, 5 and 6 prove parts (a), (b), (c) and (d). Appendix § 8 describes the certificates, Appendix B contains the omitted proofs, and Appendix C lists the inequalities that the main text does not print. We conclude in Section 7.
What is new
As far as we could determine, the following are new. First, valid balanced and superbalanced inequalities without an unscaled contraction proof in the presentation with split right-hand side, both on the full cube and on the realizable domain (Theorem 1.1 (a), (b)), the smallest of them with six parties. The earlier failures that we know of are failures of the presentation with merged right-hand side [19 , 16 ] . In particular, the answer to Problem 3 of Avis and Hernández-Cuenca [19 ] , in the formulation stated in § 2.4 , is negative. For four of the seven-party superbalanced examples, E 0 E_0 E 0 E 1 E_1 E 1 E 3 E_3 E 3 E 4 E_4 E 4 k min = 2 k_{\min}=2 k m i n = 2 Theorem 1.1 (d)). Second, the description of the scaling spectrum of star inequalities by lattice points of a polytope, the construction of star inequalities from coin weighings, with the explicit family D j D_j D j 2 ( N + 1 ) / 4 2^{(N+1)/4} 2 ( N + 1 ) /4 N ( 1 / 4 − o ( 1 ) ) N N^{(1/4-o(1))N} N ( 1/4 − o ( 1 )) N N ( 1 / 2 + o ( 1 ) ) N N^{(1/2+o(1))N} N ( 1/2 + o ( 1 )) N N N N [26 ] , who use them for coin-weighing problems (see also [28 ] ). In the literature we read we found no earlier statement that scaling beyond small factors can be necessary. Third, the superbalanced facet F 7 F_7 F 7 H E C 7 \mathrm{HEC}_7 HEC 7 § 5 ), together with its unscaled map on the realizable domain, which necessarily breaks the symmetry of F 7 F_7 F 7 [6 ] , the realizable domain to Avis and Hernández-Cuenca [19 ] , and the superbalance of facets to He, Hubeny and Rangamani [25 ] .
Preliminaries: contraction maps and the realizable domain
In this section we fix graph models and the holographic entropy cone, the Bell-pair conditions that define balanced and superbalanced inequalities, contraction maps in the count form used by our map and non-existence certificates, and the realizable domain. Two lemmas at the end are used throughout Sections 3–5: Lemma 2.13 proves validity from a real-valued map on the realizable domain, and Lemma 2.15 transfers non-existence from a small subdomain to the full cube and to the realizable domain.
Graph models and the holographic entropy cone
A graph model is a finite undirected graph ( V , E ) (V,E) ( V , E ) w e ≥ 0 w_e \ge0 w e ≥ 0 b : ∂ V → [ N ] ∪ { O } b:\partial V \to[N]\cup\{O\} b : ∂ V → [ N ] ∪ { O } ∂ V ⊆ V \partial V \subseteq V ∂ V ⊆ V I ⊆ [ N ] I \subseteq[N] I ⊆ [ N ] I I I W ⊆ V W \subseteq V W ⊆ V W ∩ ∂ V = b − 1 ( I ) W \cap\partial V=b^{-1}(I) W ∩ ∂ V = b − 1 ( I ) C ( W ) C(W) C ( W ) W W W I I I S ( I ) = min { C ( W ) : W an I -cut } S(I)=\min\{C(W): W\text{ an }I\text{-cut}\} S ( I ) = min { C ( W ) : W an I -cut } min cut of I I I C ( W ) = C ( V ∖ W ) C(W)=C(V\setminus W) C ( W ) = C ( V ∖ W ) O O O [ N ] ∪ { O } [N]\cup\{O\} [ N ] ∪ { O } H E C N ⊂ R 2 N − 1 \mathrm{HEC}_N\subset\mathbb{R}^{2^N-1} HEC N ⊂ R 2 N − 1 S = ( S ( I ) ) ∅ ≠ I ⊆ [ N ] S=(S(I))_{\varnothing\ne I\subseteq[N]} S = ( S ( I ) ) ∅ = I ⊆ [ N ] [6 ] . It is full-dimensional [19 ] .
An entropy inequality is written
Q : ∑ l = 1 L α l S ( I l ) ≥ ∑ r = 1 R β r S ( J r ) , (2) Q:\qquad\sum_{l=1}^{L}\alpha_l S(I_l)\ge\sum_{r=1}^{R}\beta_r S(J_r), \tag*{(2)} Q : l = 1 ∑ L α l S ( I l ) ≥ r = 1 ∑ R β r S ( J r ) , (2) with L L L R R R α l , β r \alpha_l,\beta_r α l , β r I l , J r ⊆ [ N ] I_l,J_r\subseteq[N] I l , J r ⊆ [ N ] I l I_l I l J r J_r J r I l I_l I l J r J_r J r Q ∈ Z 2 N − 1 Q\in\mathbb{Z}^{2^N-1} Q ∈ Z 2 N − 1 Q ⋅ S ≥ 0 Q\cdot S\ge0 Q ⋅ S ≥ 0 ∣ α ∣ = ∑ l α l |\alpha|=\sum_l\alpha_l ∣ α ∣ = ∑ l α l ∣ β ∣ = ∑ r β r |\beta|=\sum_r\beta_r ∣ β ∣ = ∑ r β r Q ⋅ S ≥ 0 Q\cdot S\ge0 Q ⋅ S ≥ 0 Q ≠ 0 Q\ne0 Q = 0 facet of H E C N \mathrm{HEC}_N HEC N H E C N ∩ Q ⊥ \mathrm{HEC}_N\cap Q^\perp HEC N ∩ Q ⊥ 2 N − 2 2^N-2 2 N − 2 H E C N \mathrm{HEC}_N HEC N 2 N − 2 2^N-2 2 N − 2 Q Q Q [19 ] ). We call such graph models tight . For pairwise disjoint nonempty X , Y , Z ⊆ [ N ] X,Y,Z\subseteq[N] X , Y , Z ⊆ [ N ]
S ( X ) + S ( Y ) ≥ S ( X Y ) , S ( X Y ) + S ( X Z ) + S ( Y Z ) ≥ S ( X ) + S ( Y ) + S ( Z ) + S ( X Y Z ) , (3) S(X)+S(Y)\ge S(XY),\qquad S(XY)+S(XZ)+S(YZ)\ge S(X)+S(Y)+S(Z)+S(XYZ), \tag*{(3)} S ( X ) + S ( Y ) ≥ S ( X Y ) , S ( X Y ) + S ( X Z ) + S ( Y Z ) ≥ S ( X ) + S ( Y ) + S ( Z ) + S ( X Y Z ) , (3) where X Y = X ∪ Y XY=X\cup Y X Y = X ∪ Y [4 ] ; see also [6 , 29 ] for proofs by contraction and by bit threads. The symmetric group S N + 1 \mathfrak{S}_{N+1} S N + 1 [ N ] ∪ { O } [N]\cup\{O\} [ N ] ∪ { O } R 2 N − 1 \mathbb{R}^{2^{N}-1} R 2 N − 1 H E C N \mathrm{HEC}_{N} HEC N [6 ] . The stabilizer Stab ( Q ) ⊆ S N + 1 \operatorname{Stab}(Q)\subseteq\mathfrak{S}_{N+1} Stab ( Q ) ⊆ S N + 1 Q Q Q
Bell pairs, balance and superbalance
For distinct i , j ∈ [ N ] ∪ { O } i,j\in[N]\cup\{O\} i , j ∈ [ N ] ∪ { O } Bell-pair vector r i j r_{ij} r ij 1 1 1 i i i j j j [6 , 25 ] : r i j ( I ) = 1 r_{ij}(I)=1 r ij ( I ) = 1 I I I i , j i,j i , j 0 0 0 occurrence words x ( i ) ∈ { 0 , 1 } L x^{(i)}\in\{0,1\}^{L} x ( i ) ∈ { 0 , 1 } L y ( i ) ∈ { 0 , 1 } R y^{(i)}\in\{0,1\}^{R} y ( i ) ∈ { 0 , 1 } R i i i
x l ( i ) = [ i ∈ I l ] , y r ( i ) = [ i ∈ J r ] , (4) x^{(i)}_{l}=[i\in I_l],\qquad y^{(i)}_{r}=[i\in J_r], \tag*{(4)} x l ( i ) = [ i ∈ I l ] , y r ( i ) = [ i ∈ J r ] , (4) and x ( O ) = 0 x^{(O)}=0 x ( O ) = 0 y ( O ) = 0 y^{(O)}=0 y ( O ) = 0
d α ( u , v ) = ∑ l = 1 L α l ∣ u l − v l ∣ , u , v ∈ { 0 , 1 } L , (5) d_{\alpha}(u,v)=\sum_{l=1}^{L}\alpha_l|u_l-v_l|,\qquad u,v\in\{0,1\}^{L}, \tag*{(5)} d α ( u , v ) = l = 1 ∑ L α l ∣ u l − v l ∣ , u , v ∈ { 0 , 1 } L , (5) and d β d_{\beta} d β { 0 , 1 } R \{0,1\}^{R} { 0 , 1 } R S ( I ) S(I) S ( I ) 1 1 1 r i j r_{ij} r ij I I I i i i j j j Bell value of Q Q Q i , j i,j i , j
Q ⋅ r i j = d α ( x ( i ) , x ( j ) ) − d β ( y ( i ) , y ( j ) ) . (6) Q\cdot r_{ij}=d_{\alpha}(x^{(i)},x^{(j)})-d_{\beta}(y^{(i)},y^{(j)}). \tag*{(6)} Q ⋅ r ij = d α ( x ( i ) , x ( j ) ) − d β ( y ( i ) , y ( j ) ) . (6) A valid inequality has nonnegative Bell values. The inequality Q Q Q balanced if Q ⋅ r i O = 0 Q\cdot r_{iO}=0 Q ⋅ r i O = 0 i i i [6 ] , and superbalanced if Q ⋅ r i j = 0 Q\cdot r_{ij}=0 Q ⋅ r ij = 0 i , j ∈ [ N ] ∪ { O } i,j\in[N]\cup\{O\} i , j ∈ [ N ] ∪ { O } [16 ] is equivalent to the form of He, Hubeny and Rangamani [25 ] , that Q Q Q [24 ] , because the relabeling that exchanges j j j O O O r i O r_{iO} r i O r i j r_{ij} r ij H E C N \mathrm{HEC}_{N} HEC N [25 ] . Instances of MMI are superbalanced.
Contraction maps in count form
Bao et al. proved an inequality valid by a map between Boolean cubes that respects the occurrence words and does not increase weighted Hamming distances [6 ] . A coefficient β r \beta_r β r β r \beta_r β r S ( J r ) S(J_r) S ( J r ) [6 , 30 ] . Whether a map exists depends on this choice [19 , 16 ] . We merge the left-hand side, split the right-hand side, and record a map by how many of the β r \beta_r β r
Definition 2.6 (Count maps). Let Q Q Q Ω ⊂ { 0 , 1 } L \Omega\subset\{0,1\}^{L} Ω ⊂ { 0 , 1 } L x ( i ) x^{(i)} x ( i ) i ∈ [ N ] i\in[N] i ∈ [ N ] 0 0 0 real map for Q Q Q Ω \Omega Ω n = ( n r ) r = 1 R : Ω → ∏ r = 1 R [ 0 , β r ] \mathbf{n}=(n_r)_{r=1}^{R}:\Omega\to\prod_{r=1}^{R}[0,\beta_r] n = ( n r ) r = 1 R : Ω → ∏ r = 1 R [ 0 , β r ]
n r ( x ( i ) ) = β r [ i ∈ J r ] for all i ∈ [ N ] and all r , n ( 0 ) = 0 , (7) n_r(x^{(i)})=\beta_r[i\in J_r]\quad\text{for all }i\in[N]\text{ and all }r,\qquad n(0)=0, \tag*{(7)} n r ( x ( i ) ) = β r [ i ∈ J r ] for all i ∈ [ N ] and all r , n ( 0 ) = 0 , (7) and
∑ r = 1 R ∣ n r ( u ) − n r ( v ) ∣ ≤ d α ( u , v ) for all u , v ∈ Ω . (8) \sum_{r=1}^{R}|n_r(u)-n_r(v)|\le d_{\alpha}(u,v)\quad\text{for all }u,v\in\Omega. \tag*{(8)} r = 1 ∑ R ∣ n r ( u ) − n r ( v ) ∣ ≤ d α ( u , v ) for all u , v ∈ Ω. (8) It is an integer map , or an unscaled map , if n r ( u ) ∈ { 0 , 1 , … , β r } n_r(u)\in\{0,1,\ldots,\beta_r\} n r ( u ) ∈ { 0 , 1 , … , β r } u u u r r r k ≥ 1 k\ge1 k ≥ 1 k Q kQ k Q k α l k\alpha_l k α l k β r k\beta_r k β r
The conditions (2.7) are the pins , and the condition at 0 0 0 Ω = { 0 , 1 } L \Omega=\{0,1\}^{L} Ω = { 0 , 1 } L full cube , and say that Q Q Q unscaled contraction proof on a domain if it has an integer map there. Write y ˉ ( i ) ∈ { 0 , 1 } ∣ β ∣ \bar{y}^{(i)}\in\{0,1\}^{|\beta|} y ˉ ( i ) ∈ { 0 , 1 } ∣ β ∣ i i i β r \beta_r β r ( r , 1 ) , … , ( r , β r ) (r,1),\ldots,(r,\beta_r) ( r , 1 ) , … , ( r , β r ) S ( J r ) S(J_r) S ( J r ) y ˉ r , s ( i ) = y r ( i ) \bar{y}^{(i)}_{r,s}=y^{(i)}_r y ˉ r , s ( i ) = y r ( i ) d 1 d_1 d 1 { 0 , 1 } ∣ β ∣ \{0,1\}^{|\beta|} { 0 , 1 } ∣ β ∣
Lemma 2.9 (Count maps are split-RHS contraction maps). Let Ω \Omega Ω Definition 2.6 . The inequality Q Q Q Ω \Omega Ω f : Ω → { 0 , 1 } ∣ β ∣ f:\Omega\to\{0,1\}^{|\beta|} f : Ω → { 0 , 1 } ∣ β ∣ f ( x ( i ) ) = y ( i ) f(x^{(i)})=y^{(i)} f ( x ( i ) ) = y ( i ) i ∈ [ N ] i\in[N] i ∈ [ N ] f ( 0 ) = 0 f(0)=0 f ( 0 ) = 0 d 1 ( f ( u ) , f ( v ) ) ≤ d α ( u , v ) d_1(f(u),f(v))\le d_\alpha(u,v) d 1 ( f ( u ) , f ( v )) ≤ d α ( u , v ) u , v ∈ Ω u,v\in\Omega u , v ∈ Ω
The proof, by sorting the copies of each term, is in Appendix B.§ 1 . On the full cube, an integer map is therefore a contraction map of Bao et al. for the presentation with split right-hand side, and their theorem [6 ] shows that Q Q Q Q Q Q α l \alpha_l α l β r \beta_r β r f f f Q Q Q { 0 , 1 } L \{0,1\}^{L} { 0 , 1 } L f f f { 0 , 1 } ∣ β ∣ \{0,1\}^{|\beta|} { 0 , 1 } ∣ β ∣ [16 ] . On the left, the map δ \delta δ l l l u ∈ { 0 , 1 } L u\in\{0,1\}^{L} u ∈ { 0 , 1 } L α l \alpha_l α l 0 0 0 0 0 0 δ \delta δ { 0 , 1 } L \{0,1\}^{L} { 0 , 1 } L Lemma 2.9 . So every statement in this paper that Q Q Q Q Q Q [19 , 16 ] .
A real map for k Q kQ k Q k k k Q Q Q
Definition 2.10 (Least scaling). For a valid inequality Q Q Q k min ( Q ) k_{\min}(Q) k m i n ( Q ) k ≥ 1 k\ge1 k ≥ 1 k Q kQ k Q { 0 , 1 } L \{0,1\}^{L} { 0 , 1 } L k min A ( Q ) k_{\min}^{A}(Q) k m i n A ( Q ) k k k k Q kQ k Q A ( Q ) \mathcal{A}(Q) A ( Q ) Definition 2.11 . Either is ∞ \infty ∞ k k k
Since A ( Q ) ⊆ { 0 , 1 } L \mathcal{A}(Q)\subseteq\{0,1\}^{L} A ( Q ) ⊆ { 0 , 1 } L k min A ( Q ) ≤ k min ( Q ) k_{\min}^{A}(Q)\le k_{\min}(Q) k m i n A ( Q ) ≤ k m i n ( Q ) n n n k 1 Q k_1Q k 1 Q n ′ n' n ′ k 2 Q k_2Q k 2 Q n + n ′ n+n' n + n ′ ( k 1 + k 2 ) Q (k_1+k_2)Q ( k 1 + k 2 ) Q k k k k Q kQ k Q M M M M n Mn M n M Q MQ M Q
The realizable domain
In the proof of Bao et al., every vertex of a graph model receives the word that records which of the chosen LHS min cuts contain it. If the min cuts are chosen minimal, these words satisfy two conditions, and the map is needed only on the words that satisfy them [19 , 16 ] . On the role of nesting in contraction proofs see [15 ] .
Definition 2.11 (Realizable domain). The realizable domain A ( Q ) ⊆ { 0 , 1 } L \mathcal{A}(Q)\subseteq\{0,1\}^{L} A ( Q ) ⊆ { 0 , 1 } L Q Q Q x x x
(R1) if x l = x l ′ = 1 x_l=x_{l'}=1 x l = x l ′ = 1 I l ∩ I l ′ ≠ ∅ I_l\cap I_{l'}\ne\varnothing I l ∩ I l ′ = ∅
(R2) if x l = 1 x_l=1 x l = 1 I l ⊆ I l ′ I_l\subseteq I_{l'} I l ⊆ I l ′ x l ′ = 1 x_{l'}=1 x l ′ = 1
This is the domain of Avis and Hernández-Cuenca [19 ] , who describe its elements through the antichains of their minimal elements; it is called the realizable subset in [16 ] . It is defined through the terms I l ⊆ [ N ] I_l\subseteq[N] I l ⊆ [ N ] O O O n ( 0 ) = 0 n(0)=0 n ( 0 ) = 0 O O O A ( Q ) \mathcal{A}(Q) A ( Q ) Q Q Q O O O A ( k Q ) = A ( Q ) \mathcal{A}(kQ)=\mathcal{A}(Q) A ( k Q ) = A ( Q ) 0 0 0 x ( i ) x^{(i)} x ( i ) [6 ] , but it can be reduced to the following pairs.
Lemma 2.12 (Irreducible pairs). Let Ω ⊆ { 0 , 1 } L \Omega\subseteq\{0,1\}^{L} Ω ⊆ { 0 , 1 } L u , v ∈ Ω u,v\in\Omega u , v ∈ Ω Ω \Omega Ω z ∈ Ω ∖ { u , v } z\in\Omega\setminus\{u,v\} z ∈ Ω ∖ { u , v } z l = u l z_l=u_l z l = u l u l = v l u_l=v_l u l = v l n : Ω → R n:\Omega\to\mathbb{R} n : Ω → R
The proof is a short induction (Appendix B.§ 1 ). On the full cube the irreducible pairs are the pairs at Hamming distance 1. We can now state the criterion behind our validity maps.
Lemma 2.13 (Realizable-domain criterion). Let Q Q Q (2) . Suppose there is a map n : A ( Q ) → ∏ r = 1 R [ 0 , β r ] n:\mathcal{A}(Q) \to\prod_{r=1}^{R}[0,\beta_r] n : A ( Q ) → ∏ r = 1 R [ 0 , β r ] n r ( x ( i ) ) = β r [ i ∈ J r ] n_r(x^{(i)})=\beta_r[i\in J_r] n r ( x ( i ) ) = β r [ i ∈ J r ] i ∈ [ N ] i\in[N] i ∈ [ N ] r r r n ( 0 ) = 0 n(0)=0 n ( 0 ) = 0 ∑ r ∣ n r ( u ) − n r ( v ) ∣ ≤ d α ( u , v ) \sum_r |n_r(u)-n_r(v)|\le d_{\alpha}(u,v) ∑ r ∣ n r ( u ) − n r ( v ) ∣ ≤ d α ( u , v ) u , v ∈ A ( Q ) u,v\in\mathcal{A}(Q) u , v ∈ A ( Q ) Lemma 2.12 , for all pairs irreducible in A ( Q ) \mathcal{A}(Q) A ( Q ) Q Q Q H E C N \mathrm{HEC}_N HEC N
The proof is in Appendix B.§ 2 . Each vertex of a graph model receives the word that records which minimal min cuts of the LHS terms contain it, as in [6 , 19 ] ; these words lie in A ( Q ) \mathcal{A}(Q) A ( Q ) [19 ] ; and each RHS term is bounded by integrating the weights of the threshold cuts { v : n r ( v ) > t } \{v:n_r(v)>t\} { v : n r ( v ) > t } t t t
For maps of the form n r = β r f r n_r=\beta_r f_r n r = β r f r f : A ( Q ) → { 0 , 1 } R f:\mathcal{A}(Q)\to\{0,1\}^{R} f : A ( Q ) → { 0 , 1 } R ∑ r ∣ n r ( u ) − n r ( v ) ∣ = d β ( f ( u ) , f ( v ) ) \sum_r|n_r(u)-n_r(v)|=d_{\beta}(f(u),f(v)) ∑ r ∣ n r ( u ) − n r ( v ) ∣ = d β ( f ( u ) , f ( v )) [19 ] . Grimaldi, Headrick, Hubeny and Shteyner record that a contraction map on the realizable domain proves validity [16 ] . For maps with rational values, which are all our validity certificates, Lemma 2.13 also follows from the proof of the theorem of Avis and Hernández-Cuenca: if M M M n n n M n Mn M n M Q MQ M Q Lemma 2.9 with Ω = A ( Q ) \Omega=\mathcal{A}(Q) Ω = A ( Q ) { 0 , 1 } \{0,1\} { 0 , 1 } [19 ] , although the theorem is stated for distinct terms. The proof in Appendix B.§ 2 covers real values directly.
Avis and Hernández-Cuenca ask in their Problem 3 whether the existence of a contraction map on their domain becomes a necessary condition for validity once every RHS term β r S ( J r ) \beta_r S(J_r) β r S ( J r ) β r ≥ 2 \beta_r\ge2 β r ≥ 2 β r \beta_r β r [19 ] . By Lemma 2.9 with Ω = A ( Q ) \Omega=\mathcal{A}(Q) Ω = A ( Q ) k min A ( Q ) = 1 k_{\min}^{\mathcal{A}}(Q)=1 k m i n A ( Q ) = 1 Q Q Q
Restriction to a subdomain
To show that Q Q Q A A A
U ( Q ) = { x ( 1 ) , … , x ( N ) , 0 } ∪ [ 0 , x ( A ) ] , [ 0 , x ( A ) ] = { x ∈ { 0 , 1 } L : x l ≤ x l ( A ) for all l } , (9) U(Q)=\{x^{(1)},\ldots,x^{(N)},0\}\cup[0,x^{(A)}],\qquad[0,x^{(A)}]=\{x\in\{0,1\}^{L}:x_l\le x_l^{(A)}\text{ for all }l\}, \tag*{(9)} U ( Q ) = { x ( 1 ) , … , x ( N ) , 0 } ∪ [ 0 , x ( A ) ] , [ 0 , x ( A ) ] = { x ∈ { 0 , 1 } L : x l ≤ x l ( A ) for all l } , (9) the occurrence words together with the 2 L A 2^{L_A} 2 L A L A L_A L A A A A
Lemma 2.15 (Restriction). Let k ≥ 1 k\ge1 k ≥ 1 k Q kQ k Q U ( Q ) U(Q) U ( Q ) k Q kQ k Q { 0 , 1 } L \{0,1\}^{L} { 0 , 1 } L U ( Q ) ⊆ A ( Q ) U(Q)\subseteq\mathcal{A}(Q) U ( Q ) ⊆ A ( Q ) A A A k Q kQ k Q U ( Q ) U(Q) U ( Q ) k Q kQ k Q A ( Q ) \mathcal{A}(Q) A ( Q )
Proof. (a) A map on { 0 , 1 } L \{0,1\}^{L} { 0 , 1 } L 0 0 0 x ∈ [ 0 , x ( A ) ] x\in[0,x^{(A)}] x ∈ [ 0 , x ( A ) ] x l = x l ′ = 1 x_l=x_{l'}=1 x l = x l ′ = 1 A A A x l = 1 x_l=1 x l = 1 I l ⊆ I l ′ I_l\subseteq I_{l'} I l ⊆ I l ′ A ∈ I l ′ A\in I_{l'} A ∈ I l ′ A A A l ′ = l l'=l l ′ = l I l ⊆ I l ′ I_l\subseteq I_{l'} I l ⊆ I l ′ A A A l l l [ 0 , x ( A ) ] [0,x^{(A)}] [ 0 , x ( A ) ]
By Lemma 2.12 , the contraction condition on U ( Q ) U(Q) U ( Q ) U ( Q ) U(Q) U ( Q )
Balanced inequalities without unscaled proofs
Our example has seven parties, and its failure can be checked by hand at a single point of the cube, where the contraction conditions reduce to covering the vertices of two disjoint triangles by edges.
Let N = 7 N=7 N = 7 A , … , G A,\ldots,G A , … , G A A A { B , C , D } \{B,C,D\} { B , C , D } { E , F , G } \{E,F,G\} { E , F , G } E = { B C , B D , C D , E F , E G , F G } \mathcal{E}=\{BC,BD,CD,EF,EG,FG\} E = { B C , B D , C D , E F , E G , F G }
B 7 ∗ : 2 A + A O + 3 ( B O + C O + D O + E O + F O + G O ) ≥ A B C + A B D + A C D + A E F + A E G + A F G + 14 O . (10) B_7^*: \quad2A+AO+3(BO+CO+DO+EO+FO+GO) \ge ABC+ABD+ACD+AEF+AEG+AFG+14O . \tag*{(10)} B 7 ∗ : 2 A + A O + 3 ( B O + C O + D O + E O + F O + GO ) ≥ A B C + A B D + A C D + A E F + A E G + A F G + 14 O . (10) By purification A O AO A O S ( B C D E F G ) S(BCDEFG) S ( B C D E F G ) i O iO i O i i i O O O S ( A B C D E F G ) S(ABCDEFG) S ( A B C D E F G ) B 7 ∗ B_7^* B 7 ∗ L = 8 L=8 L = 8 ∣ α ∣ = 21 |\alpha|=21 ∣ α ∣ = 21 R = 7 R=7 R = 7 S ( A ϵ ) S(A\epsilon) S ( A ϵ ) ϵ ∈ E \epsilon\in\mathcal{E} ϵ ∈ E β = 1 \beta=1 β = 1 S ( A B C D E F G ) S(ABCDEFG) S ( A B C D E F G ) β = 14 \beta=14 β = 14 ∣ β ∣ = 20 |\beta|=20 ∣ β ∣ = 20 B 7 ∗ B_7^* B 7 ∗ B 7 ∗ B_7^* B 7 ∗
Proposition 3.2. The inequality B 7 ∗ B_7^* B 7 ∗
(i) It is a nonnegative combination, with coefficients in 1 2 Z \frac{1}{2}\mathbb{Z} 2 1 Z
(ii) 2 B 7 ∗ 2B_7^* 2 B 7 ∗ { 0 , 1 } 8 \{0,1\}^8 { 0 , 1 } 8
(iii) B 7 ∗ B_7^* B 7 ∗ A ( B 7 ∗ ) \mathcal{A}(B_7^*) A ( B 7 ∗ )
Hence k min ( B 7 ∗ ) = k min A ( B 7 ∗ ) = 2 k_{\min}(B_7^*)=k_{\min}^{A}(B_7^*)=2 k m i n ( B 7 ∗ ) = k m i n A ( B 7 ∗ ) = 2
Part (i) is an identity between integer vectors with 26 instances of subadditivity and 17 of MMI, with coefficients in { 1 2 , 1 , 3 2 , 2 } \{\frac{1}{2},1,\frac{3}{2},2\} { 2 1 , 1 , 2 3 , 2 } { 0 , 1 } 8 \{0,1\}^8 { 0 , 1 } 8 A ( B 7 ∗ ) \mathcal{A}(B_7^*) A ( B 7 ∗ )
Proof of Proposition 3.2(iii). Order the LHS terms as S ( A ) S(A) S ( A ) S ( A O ) S(AO) S ( A O ) S ( i O ) S(iO) S ( i O ) i ∈ { B , … , G } i\in\{B,\ldots,G\} i ∈ { B , … , G } A A A S ( A ) S(A) S ( A ) S ( i O ) S(iO) S ( i O ) i O iO i O A A A S ( A O ) S(AO) S ( A O ) i ∈ { B , … , G } i\in\{B,\ldots,G\} i ∈ { B , … , G } S ( A O ) S(AO) S ( A O ) S ( j O ) S(jO) S ( j O ) j ≠ i j\ne i j = i S ( A ) S(A) S ( A ) S ( i O ) S(iO) S ( i O ) z ∈ { 0 , 1 } 8 z\in\{0,1\}^8 z ∈ { 0 , 1 } 8 S ( A ) S(A) S ( A )
d α ( z , x ( A ) ) = 2 + 1 = 3 , d α ( z , x ( i ) ) = 3 ( i ∈ { B , … , G } ) , d α ( z , 0 ) = 1 + 6 ⋅ 3 = 19. (11) d_{\alpha}(z,x^{(A)})=2+1=3,\qquad d_{\alpha}(z,x^{(i)})=3\quad(i\in\{B,\ldots,G\}),\qquad d_{\alpha}(z,0)=1+6\cdot3=19. \tag*{(11)} d α ( z , x ( A ) ) = 2 + 1 = 3 , d α ( z , x ( i ) ) = 3 ( i ∈ { B , … , G }) , d α ( z , 0 ) = 1 + 6 ⋅ 3 = 19. (11) The point z z z A ( B 7 ∗ ) \mathcal{A}(B_7^*) A ( B 7 ∗ ) z z z S ( A O ) S(AO) S ( A O ) S ( i O ) S(iO) S ( i O ) [ N ] ∖ { A } [N]\setminus\{A\} [ N ] ∖ { A } [ N ] ∖ { i } [N]\setminus\{i\} [ N ] ∖ { i } A ⊆ i O A\subseteq iO A ⊆ i O z z z z z z S ( A ) S(A) S ( A ) A ( B 7 ∗ ) \mathcal{A}(B_7^*) A ( B 7 ∗ ) n ( z ) n(z) n ( z ) z z z x ( A ) , … , x ( G ) , 0 x^{(A)},\ldots,x^{(G)},0 x ( A ) , … , x ( G ) , 0
Write a candidate value as n ( z ) = ( θ , 14 − t ) n(z)=(\theta,14-t) n ( z ) = ( θ , 14 − t ) θ = ( θ ϵ ) ϵ ∈ E ∈ [ 0 , 1 ] E \theta=(\theta_{\epsilon})_{\epsilon\in\mathcal{E}}\in[0,1]^{\mathcal{E}} θ = ( θ ϵ ) ϵ ∈ E ∈ [ 0 , 1 ] E S ( A ϵ ) S(A_{\epsilon}) S ( A ϵ ) 14 − t ∈ [ 0 , 14 ] 14-t\in[0,14] 14 − t ∈ [ 0 , 14 ] S ( A B C D E F G ) S(ABCDEFG) S ( A B C D E F G ) n ( x ( A ) ) n(x^{(A)}) n ( x ( A ) ) S ( A ϵ ) S(A_{\epsilon}) S ( A ϵ ) n ( x ( i ) ) n(x^{(i)}) n ( x ( i ) ) i ∈ { B , … , G } i\in\{B,\ldots,G\} i ∈ { B , … , G } [ i ∈ ϵ ] [i\in\epsilon] [ i ∈ ϵ ] S ( A ϵ ) S(A_{\epsilon}) S ( A ϵ ) S ( A B C D E F G ) S(ABCDEFG) S ( A B C D E F G ) n ( 0 ) = 0 n(0)=0 n ( 0 ) = 0
( A ) : ∑ ϵ ( 1 − θ ϵ ) + t ≤ 3 , ( i ) : ∑ ϵ ∣ θ ϵ − [ i ∈ ϵ ] ∣ + t ≤ 3 , ( O ) : ∑ ϵ θ ϵ + 14 − t ≤ 19. (12) \begin{aligned}
(A):\quad&\sum_{\epsilon}(1-\theta_{\epsilon})+t\leq3, \qquad
(i):\quad\sum_{\epsilon}\lvert\theta_{\epsilon}-[i\in\epsilon]\rvert+t\leq3, \qquad
(O):\quad\sum_{\epsilon}\theta_{\epsilon}+14-t\leq19. \tag*{(12)}
\end{aligned} ( A ) : ϵ ∑ ( 1 − θ ϵ ) + t ≤ 3 , ( i ) : ϵ ∑ ∣ θ ϵ − [ i ∈ ϵ ]∣ + t ≤ 3 , ( O ) : ϵ ∑ θ ϵ + 14 − t ≤ 19. (12) For each vertex i i i E i ⊂ E \mathcal{E}_i\subset\mathcal{E} E i ⊂ E i i i
Suppose n ( z ) n(z) n ( z ) θ \theta θ C ⊆ E C\subseteq\mathcal{E} C ⊆ E t t t ( i ) (i) ( i ) ∣ C ∣ + 2 − 2 ∣ C ∩ E i ∣ + t ≤ 3 \lvert C\rvert+2-2\lvert C\cap\mathcal{E}_i\rvert+t\leq3 ∣ C ∣ + 2 − 2 ∣ C ∩ E i ∣ + t ≤ 3 ( A ) (A) ( A ) 6 − ∣ C ∣ + t ≤ 3 6-\lvert C\rvert+t\leq3 6 − ∣ C ∣ + t ≤ 3 ∣ C ∣ ≥ 3 \lvert C\rvert\geq3 ∣ C ∣ ≥ 3 ∣ C ∣ = 3 \lvert C\rvert=3 ∣ C ∣ = 3 ( A ) (A) ( A ) t = 0 t=0 t = 0 ( i ) (i) ( i ) ∣ C ∩ E i ∣ ≥ 1 \lvert C\cap\mathcal{E}_i\rvert\geq1 ∣ C ∩ E i ∣ ≥ 1 C C C E \mathcal{E} E C C C ∣ C ∣ ≥ 4 \lvert C\rvert\geq4 ∣ C ∣ ≥ 4 ∣ C ∣ ≥ 4 \lvert C\rvert\geq4 ∣ C ∣ ≥ 4 ( i ) (i) ( i ) 2 ∣ C ∩ E i ∣ ≥ ∣ C ∣ − 1 ≥ 3 2\lvert C\cap\mathcal{E}_i\rvert\geq\lvert C\rvert-1\geq3 2 ∣ C ∩ E i ∣ ≥ ∣ C ∣ − 1 ≥ 3 ∣ C ∩ E i ∣ = 2 \lvert C\cap\mathcal{E}_i\rvert=2 ∣ C ∩ E i ∣ = 2 i i i C C C C = E C=\mathcal{E} C = E ( i ) (i) ( i ) 6 + 2 − 4 + t ≤ 3 6+2-4+t\leq3 6 + 2 − 4 + t ≤ 3 z z z z z z { 0 , 1 } 8 \{0,1\}^{8} { 0 , 1 } 8 A ( B 7 ∗ ) A(B_7^*) A ( B 7 ∗ )
The real relaxation is feasible at z z z θ ϵ = 1 2 \theta_{\epsilon}=\frac{1}{2} θ ϵ = 2 1 t = 0 t=0 t = 0 3 ≤ 3 3\leq3 3 ≤ 3 ( A ) (A) ( A ) 1 2 ⋅ 6 = 3 ≤ 3 \frac{1}{2}\cdot6=3\leq3 2 1 ⋅ 6 = 3 ≤ 3 ( i ) (i) ( i ) 17 ≤ 19 17\leq19 17 ≤ 19 ( O ) (O) ( O ) Figure 1 ): two disjoint triangles have fractional edge cover number 3 but need four edges in an integral cover. The point z z z x ( i ) x^{(i)} x ( i ) x ( j ) x^{(j)} x ( j )
Figure 1. The structure of B 7 ∗ B_7^* B 7 ∗ S ( A ϵ ) S(A\epsilon) S ( A ϵ ) A A A z z z 1 2 \frac{1}{2} 2 1
Remark 3.5 (A second example). The balanced inequality
B 7 : 3 ( A O + B O + C O + D O + E O + F O + G O ) + D E F G ≥ A B C + A D E + A F G + B D E F + B D E G + C D F G + C E F G + 15 O \begin{aligned}
B_7:\quad3(AO+BO+CO+DO+EO+FO+GO)+DEFG \\
&\geq ABC+ADE+AFG+BDEF+BDEG+CDFG+CEFG+15O
\end{aligned} B 7 : 3 ( A O + B O + C O + D O + E O + F O + GO ) + D E F G ≥ A B C + A D E + A F G + B D E F + B D E G + C D F G + C E F G + 15 O is a nonnegative 1 2 Z \frac{1}{2}\mathbb{Z} 2 1 Z k min ( B 7 ) = 2 k_{\min}(B_7)=2 k m i n ( B 7 ) = 2 Table 4 ), but its obstruction is not visible at one point: the contraction conditions against the pinned points force integer values at two points of { 0 , 1 } 8 \{0,1\}^{8} { 0 , 1 } 8 ℓ 1 \ell^1 ℓ 1
Table 4. The certificates. “Map” means an integer map for the inequality as stated. Domains: the full cube, A \mathcal{A} A U \mathcal{U} U Y 7 Y_7 Y 7 (23) . The certificates of Section 6 are listed in Table 5 .
Remark 3.6 (Scope). Both B 7 ∗ B_7^* B 7 ∗ B 7 B_7 B 7 H E C 7 \mathrm{HEC}_7 HEC 7 B 7 ∗ B_7^* B 7 ∗ B 7 B_7 B 7 Q 8 A Q_8^A Q 8 A E 0 E_0 E 0 E 1 E_1 E 1 E 3 E_3 E 3 E 4 E_4 E 4 p p p p p p p p p U 6 U_6 U 6 N ≤ 5 N\leq5 N ≤ 5
Superbalanced inequalities without unscaled proofs
The obstruction of Section 3 sits at a point that lies between the occurrence words of every pair of parties, and it uses the positive Bell values of these pairs, which superbalance removes: if z z z x ( i ) x^{(i)} x ( i ) x ( j ) x^{(j)} x ( j ) i , j i,j i , j n ( z ) n(z) n ( z ) ℓ 1 \ell^1 ℓ 1 Q 8 A Q_8^A Q 8 A Q 8 Q_8 Q 8 Q = Q ′ + c X Q=Q^\prime+cX Q = Q ′ + c X c > 0 c>0 c > 0 X X X splitting . Every superbalanced inequality along the way is valid and has no unscaled map, on the full cube or on its realizable domain.
Six parties
Let N = 6 N=6 N = 6 A , … , F A,\ldots,F A , … , F { A , B , C } \{A,B,C\} { A , B , C } { D , E , F } \{D,E,F\} { D , E , F } E = { A B , A C , B C , D E , D F , E F } \mathcal{E}=\{AB,AC,BC,DE,DF,EF\} E = { A B , A C , B C , D E , D F , E F }
U 6 : A B + A C + A D + A E + A F + B C + B D + B E + B F + C D + C E + C F + D E + D F + E F + A B C + D E F + A B C D E + A B C D F + A B C E F + A B D E F + A C D E F + B C D E F ≥ 4 ( A + B + C + D + E + F ) + A B C D + A B C E + A B C F + A D E F + B D E F + C D E F + 3 A B C D E F (13) \begin{aligned}
U_6:\quad{}&AB+AC+AD+AE+AF+BC+BD+BE+BF+CD+CE+CF\\
&+DE+DF+EF+ABC+DEF+ABCDE+ABCDF+ABCEF\\
&+ABDEF+ACDEF+BCDEF\\
\ge{}&4(A+B+C+D+E+F)+ABCD+ABCE+ABCF\\
&+ADEF+BDEF+CDEF+3ABCDEF \tag*{(13)}
\end{aligned} U 6 : ≥ A B + A C + A D + A E + A F + B C + B D + B E + B F + C D + C E + C F + D E + D F + E F + A B C + D E F + A B C D E + A B C D F + A B C E F + A B D E F + A C D E F + B C D E F 4 ( A + B + C + D + E + F ) + A B C D + A B C E + A B C F + A D E F + B D E F + C D E F + 3 A B C D E F (13) has on its left-hand side the 15 pairs of parties, the two triangles and the six sets of five parties, all with coefficient 1, so L = ∣ α ∣ = 23 L=|\alpha|=23 L = ∣ α ∣ = 23 R = 13 R=13 R = 13 ∣ β ∣ = 33 |\beta|=33 ∣ β ∣ = 33 S ( ϵ O ) S(\epsilon O) S ( ϵ O ) ϵ ∈ E \epsilon\in\mathcal{E} ϵ ∈ E A B C D ABCD A B C D S ( E F O ) S(EFO) S ( E F O ) A D E F ADEF A D E F S ( B C O ) S(BCO) S ( B C O ) S ( A ϵ ) S(A\epsilon) S ( A ϵ ) B 7 ∗ B^*_7 B 7 ∗ Figure 1 ). All 21 Bell values of U 6 U_6 U 6 U 6 U_6 U 6
For a vertex i i i ϵ i \epsilon_i ϵ i i i i i j ij ij i j ‾ \overline{ij} ij x x x i i i
ψ 1 = ∑ i j ∈ E MMI ( i : j : i j ‾ ) , ψ 2 = MMI ( A : B : C ) + MMI ( D : E : F ) , ψ 3 = ∑ i j ∈ E ∑ x MMI ( i : j : x ) , ψ 4 = ∑ i ∑ x MMI ( i : x : ϵ i ) . (14) \begin{aligned}
\psi_1&=\sum_{ij\in\mathcal{E}}\operatorname{MMI}(i:j:\overline{ij}),&
\psi_2&=\operatorname{MMI}(A:B:C)+\operatorname{MMI}(D:E:F),\\
\psi_3&=\sum_{ij\in\mathcal{E}}\sum_x\operatorname{MMI}(i:j:x),&
\psi_4&=\sum_i\sum_x\operatorname{MMI}(i:x:\epsilon_i). \tag*{(14)}
\end{aligned} ψ 1 ψ 3 = ij ∈ E ∑ MMI ( i : j : ij ) , = ij ∈ E ∑ x ∑ MMI ( i : j : x ) , ψ 2 ψ 4 = MMI ( A : B : C ) + MMI ( D : E : F ) , = i ∑ x ∑ MMI ( i : x : ϵ i ) . (14) sums of 6, 2, 18 and 18 instances of MMI, where i i i ψ 4 \psi_4 ψ 4 ψ k \psi_k ψ k U 6 U_6 U 6
Proposition 4.3. The inequality U 6 U_6 U 6
(i) 6 U 6 = 3 ψ 1 + 3 ψ 2 + ψ 3 + ψ 4 6U_6=3\psi_1+3\psi_2+\psi_3+\psi_4 6 U 6 = 3 ψ 1 + 3 ψ 2 + ψ 3 + ψ 4 In particular U 6 U_6 U 6
(ii) 2 U 6 2U_6 2 U 6 A ( U 6 ) \mathcal{A}(U_6) A ( U 6 )
(iii) U 6 U_6 U 6 { 0 , 1 } 23 \{0,1\}^{23} { 0 , 1 } 23 A ( U 6 ) \mathcal{A}(U_6) A ( U 6 )
Hence k min A ( U 6 ) = 2 k_{\min}^{\mathcal{A}}(U_6)=2 k m i n A ( U 6 ) = 2
Part (i) is an identity between integer vectors, checked exactly by two programs. Part (ii) is certified by an explicit integer map whose pins, ranges and contraction condition on all 167,910 pairs of points of A ( U 6 ) \mathcal{A}(U_6) A ( U 6 ) Table 4 ). We now prove it by hand.
Proof of Proposition 4.3(iii). Let z ∈ { 0 , 1 } 23 z\in\{0,1\}^{23} z ∈ { 0 , 1 } 23 z z z A ( U 6 ) \mathcal{A}(U_6) A ( U 6 ) x ( i ) x^{(i)} x ( i ) i i i i i i i i i z z z i i i x ( i ) x^{(i)} x ( i )
d α ( z , x ( i ) ) = 5 + 1 + 1 = 7 ( i ∈ { A , … , F } ) , d α ( z , 0 ) = 6. (15) d_\alpha(z,x^{(i)})=5+1+1=7\qquad(i\in\{A,\ldots,F\}),\qquad d_\alpha(z,0)=6. \tag*{(15)} d α ( z , x ( i ) ) = 5 + 1 + 1 = 7 ( i ∈ { A , … , F }) , d α ( z , 0 ) = 6. (15) It suffices to show that no integer value n ( z ) n(z) n ( z ) (8) between z z z x ( A ) , … , x ( F ) , 0 x^{(A)},\ldots,x^{(F)},0 x ( A ) , … , x ( F ) , 0
Write a candidate value as n ( z ) = ( a , b , c ) n(z)=(a,b,c) n ( z ) = ( a , b , c ) a i ∈ [ 0 , 4 ] a_i\in[0,4] a i ∈ [ 0 , 4 ] S ( i ) S(i) S ( i ) b ϵ ∈ [ 0 , 1 ] b_{\epsilon}\in[0,1] b ϵ ∈ [ 0 , 1 ] S ( ϵ O ) S(\epsilon O) S ( ϵ O ) ϵ ∈ E \epsilon\in E ϵ ∈ E c ∈ [ 0 , 3 ] c\in[0,3] c ∈ [ 0 , 3 ] S ( A B C D E F ) S(ABCDEF) S ( A B C D E F ) ∣ n ∣ = ∑ i a i + ∑ ϵ b ϵ + c |n|=\sum_i a_i+\sum_{\epsilon}b_{\epsilon}+c ∣ n ∣ = ∑ i a i + ∑ ϵ b ϵ + c i i i S ( ϵ O ) S(\epsilon O) S ( ϵ O ) i ∉ ϵ i\notin\epsilon i ∈ / ϵ (7) , n ( x ( i ) ) n(x^{(i)}) n ( x ( i ) ) S ( i ) S(i) S ( i ) S ( j ) S(j) S ( j ) S ( ϵ O ) S(\epsilon O) S ( ϵ O ) i ∉ ϵ i\notin\epsilon i ∈ / ϵ S ( A B C D E F ) S(ABCDEF) S ( A B C D E F ) n ( z ) n(z) n ( z ) [ 0 , β r ] [0,\beta_r] [ 0 , β r ] β r \beta_r β r ∑ r ∣ n r ( z ) − n r ( x ( i ) ) ∣ = ∣ n ∣ + 11 − 2 s i \sum_r|n_r(z)-n_r(x^{(i)})|=|n|+11-2s_i ∑ r ∣ n r ( z ) − n r ( x ( i ) ) ∣ = ∣ n ∣ + 11 − 2 s i s i = a i + ∑ ϵ ∌ i b ϵ + c s_i=a_i+\sum_{\epsilon\not\ni i}b_{\epsilon}+c s i = a i + ∑ ϵ ∋ i b ϵ + c (15) the contraction conditions at the seven pinned points read
( O ) : ∣ n ∣ ≤ 6 , ( i ) : 2 s i ≥ ∣ n ∣ + 4 ( i ∈ { A , … , F } ) . (16) \begin{aligned}
(O):\quad&|n|\le6, \qquad(i):\quad2s_i\ge|n|+4 \quad(i\in\{A,\ldots,F\}). \tag*{(16)}
\end{aligned} ( O ) : ∣ n ∣ ≤ 6 , ( i ) : 2 s i ≥ ∣ n ∣ + 4 ( i ∈ { A , … , F }) . (16) Summing ( i ) (i) ( i ) a i a_i a i b ϵ b_{\epsilon} b ϵ c c c ∑ ϵ b ϵ + 3 c ≥ 2 ∑ i a i + 12 \sum_{\epsilon}b_{\epsilon}+3c\ge2\sum_i a_i+12 ∑ ϵ b ϵ + 3 c ≥ 2 ∑ i a i + 12 ( O ) (O) ( O ) ∑ ϵ b ϵ ≤ 6 − ∑ i a i − c \sum_{\epsilon}b_{\epsilon}\le6-\sum_i a_i-c ∑ ϵ b ϵ ≤ 6 − ∑ i a i − c 2 c ≥ 3 ∑ i a i + 6 2c\ge3\sum_i a_i+6 2 c ≥ 3 ∑ i a i + 6 c ≤ 3 c\le3 c ≤ 3 a = 0 a=0 a = 0 c = 3 c=3 c = 3 ∑ ϵ b ϵ ≥ 3 \sum_{\epsilon}b_{\epsilon}\ge3 ∑ ϵ b ϵ ≥ 3 ( i ) (i) ( i ) ∑ ϵ b ϵ ≤ 3 \sum_{\epsilon}b_{\epsilon}\le3 ∑ ϵ b ϵ ≤ 3 ( O ) (O) ( O ) ∑ ϵ b ϵ = 3 \sum_{\epsilon}b_{\epsilon}=3 ∑ ϵ b ϵ = 3 ∣ n ∣ = 6 |n|=6 ∣ n ∣ = 6 ( i ) (i) ( i ) ∑ ϵ ∌ i b ϵ ≥ 2 \sum_{\epsilon\not\ni i}b_{\epsilon}\ge2 ∑ ϵ ∋ i b ϵ ≥ 2 ∑ ϵ ∋ i b ϵ ≤ 1 \sum_{\epsilon\ni i}b_{\epsilon}\le1 ∑ ϵ ∋ i b ϵ ≤ 1 i i i 2 ∑ ϵ b ϵ = 6 2\sum_{\epsilon}b_{\epsilon}=6 2 ∑ ϵ b ϵ = 6 ∑ ϵ ∋ i b ϵ = 1 \sum_{\epsilon\ni i}b_{\epsilon}=1 ∑ ϵ ∋ i b ϵ = 1 b b b i , j , k i,j,k i , j , k b i j + b i k = b i j + b j k = b i k + b j k = 1 b_{ij}+b_{ik}=b_{ij}+b_{jk}=b_{ik}+b_{jk}=1 b ij + b ik = b ij + b j k = b ik + b j k = 1 b i j = b i k = b j k = 1 2 b_{ij}=b_{ik}=b_{jk}=\frac{1}{2} b ij = b ik = b j k = 2 1 (16) is a = 0 a=0 a = 0 b ϵ = 1 2 b_{\epsilon}=\frac{1}{2} b ϵ = 2 1 c = 3 c=3 c = 3 z z z { 0 , 1 } 23 \{0,1\}^{23} { 0 , 1 } 23 A ( U 6 ) \mathcal{A}(U_6) A ( U 6 )
As for B ∗ B^* B ∗ z z z 1 2 \frac{1}{2} 2 1 Figure 1 ). The difference lies in the position of z z z z z z Proposition 3.2 lies between the occurrence words of every pair of parties, and these pairs have positive Bell values. The point z z z Proposition 4.3 lies between no two of the pinned points: the words x ( i ) x^{(i)} x ( i ) x ( j ) x^{(j)} x ( j ) i j ij ij z z z x ( i ) x^{(i)} x ( i ) i i i z z z Proposition 4.3 (i), U 6 U_6 U 6 H E C 6 \mathrm{HEC}_6 HEC 6 [16 ] . We did not decide whether 2 U 6 2U_6 2 U 6 k min ( U 6 ) ≥ 2 k_{\min}(U_6)\ge2 k m i n ( U 6 ) ≥ 2
A balanced core
Let N = 8 N=8 N = 8 A , … , H A,\ldots,H A , … , H
Q 8 A : A D E + A F G + A B C H + A B D F H + A B E G H + A C D G H + A C E F H ≥ 2 A + A B D G H + A B E F H + A C D F H + A C E G H + A B C D E F G H (17) \begin{aligned}
Q^A_8:\quad ADE+AFG+ABCH+ABDFH+ABEGH+ACDGH+ACEFH\\
\ge2A+ABDGH+ABEFH+ACDFH+ACEGH+ABCDEFGH \tag*{(17)}
\end{aligned} Q 8 A : A D E + A F G + A B C H + A B D F H + A B E G H + A C D G H + A C E F H ≥ 2 A + A B D G H + A B E F H + A C D F H + A C E G H + A B C D E F G H (17) has every term containing A A A 2 A 2A 2 A k min ( Q 8 A ) = 2 k_{\min}(Q^A_8)=2 k m i n ( Q 8 A ) = 2 2 Q 8 A 2Q^A_8 2 Q 8 A { 0 , 1 } 7 \{0,1\}^7 { 0 , 1 } 7 [6 ] . DRAT proofs certify that Q 8 A Q^A_8 Q 8 A Table 4 ).
From eight to seven parties
Let
Q 8 : A D E + A F G + A B C H + A B D F H + A B E G H + A C D G H + A C E F H + 2 ( B C D E + B C F G + B D G H + B E F H + C D F H + C E G H + D E F G ) ≥ 2 A + 4 ( B + C + D + E + F + G + H ) + D E + F G + B C H + A B D G H + A B E F H + A C D F H + A C E G H + 3 B C D E F G H + A B C D E F G H . (18) \begin{aligned}
Q_8:\quad& ADE+AFG+ABCH+ABDFH+ABEGH+ACDGH+ACEFH \\
&+2(BCDE+BCFG+BDGH+BEFH+CDFH+CEGH+DEFG)\\
&\ge2A+4(B+C+D+E+F+G+H)+DE+FG+BCH\\
&\quad+ABDG H+ABEFH+ACDFH+ACEGH+3BCDEFGH+ABCDEFGH . \tag*{(18)}
\end{aligned} Q 8 : A D E + A F G + A B C H + A B D F H + A B E G H + A C D G H + A C E F H + 2 ( B C D E + B C F G + B D G H + B E F H + C D F H + C E G H + D E F G ) ≥ 2 A + 4 ( B + C + D + E + F + G + H ) + D E + F G + B C H + A B D G H + A B E F H + A C D F H + A C E G H + 3 B C D E F G H + A B C D E F G H . (18) Its terms that contain A A A Q 8 A Q_8^A Q 8 A { B , … , H } \{B,\ldots,H\} { B , … , H } B C H BCH B C H B D F BDF B D F B E G BEG B E G C D G CDG C D G C E F CEF C E F D E H DEH D E H F G H FGH F G H B , … , H B,\ldots,H B , … , H Q 8 Q_8 Q 8 L = 14 L=14 L = 14 R = 17 R=17 R = 17 ∣ α ∣ = 21 |\alpha|=21 ∣ α ∣ = 21 ∣ β ∣ = 41 |\beta|=41 ∣ β ∣ = 41 ∣ Stab ( Q 8 ) ∣ = 8 |\operatorname{Stab}(Q_8)|=8 ∣ Stab ( Q 8 ) ∣ = 8
Q 8 Q_8 Q 8 R 8 R_8 R 8 2 ( B + C + D + E + F + G + H ) + 2 B C D E F G H 2(B+C+D+E+F+G+H)+2BCDEFGH 2 ( B + C + D + E + F + G + H ) + 2 B C D E F G H 42 R 8 42R_8 42 R 8 Q 8 = 1 3 Q 8 ′ + 2 3 R 8 Q_8=\frac{1}{3}Q'_8+\frac{2}{3}R_8 Q 8 = 3 1 Q 8 ′ + 3 2 R 8 Q 8 ′ = 3 Q 8 − 2 R 8 Q'_8=3Q_8-2R_8 Q 8 ′ = 3 Q 8 − 2 R 8 Q 8 ′ Q'_8 Q 8 ′ Q 8 − t R 8 Q_8-tR_8 Q 8 − t R 8 t ≤ 2 3 t\le\frac{2}{3} t ≤ 3 2 Q 8 ′ Q'_8 Q 8 ′ R 8 R_8 R 8 2 3 \frac{2}{3} 3 2 t t t Q 8 ′ ′ = Q 8 ′ − 3 MMI ( A : H : D E ) Q''_8=Q'_8-3\operatorname{MMI}(A:H:DE) Q 8 ′′ = Q 8 ′ − 3 MMI ( A : H : D E )
Deleting a party preserves validity [6 ] : if Q Q Q N + 1 N+1 N + 1 S ( I ) S(I) S ( I ) S ( I ∖ { H } ) S(I\setminus\{H\}) S ( I ∖ { H }) N N N H H H H H H Q 8 ′ Q'_8 Q 8 ′ Q 8 ′ ′ Q''_8 Q 8 ′′
E 0 : 3 ( A B C + A D E + A F G ) + 4 ( B D G + B E F + C D F + C E G ) + 3 ( A B D F + A B E G + A C D G + A C E F ) + 4 ( B C D E + B C F G + D E F G ) ≥ 6 A + 8 ( B + C + D + E + F + G ) + 3 ( B C + D E + F G ) + 3 ( A B D G + A B E F + A C D F + A C E G ) + 5 B C D E F G + 3 A B C D E F G . (19) \begin{aligned}
E_0:\quad&3(ABC+ADE+AFG)+4(BDG+BEF+CDF+CEG)\\
&+3(ABDF+ABEG+ACDG+ACEF)+4(BCDE+BCFG+DEFG)\\
&\ge6A+8(B+C+D+E+F+G)+3(BC+DE+FG)\\
&\quad+3(ABDG+ABEF+ACDF+ACEG)+5BCDEFG+3ABCDEFG . \tag*{(19)}
\end{aligned} E 0 : 3 ( A B C + A D E + A F G ) + 4 ( B D G + B E F + C D F + C E G ) + 3 ( A B D F + A B E G + A C D G + A C E F ) + 4 ( B C D E + B C F G + D E F G ) ≥ 6 A + 8 ( B + C + D + E + F + G ) + 3 ( B C + D E + F G ) + 3 ( A B D G + A B E F + A C D F + A C E G ) + 5 B C D E F G + 3 A B C D E F G . (19) with L = 14 L=14 L = 14 R = 16 R=16 R = 16 ∣ α ∣ = 49 |\alpha|=49 ∣ α ∣ = 49 ∣ β ∣ = 83 |\beta|=83 ∣ β ∣ = 83 E 0 E_0 E 0
The descent
The seven parties of E 0 E_0 E 0 A B C ABC A B C A D E ADE A D E A F G AFG A F G B D G BDG B D G B E F BEF B E F C D F CDF C D F C E G CEG C E G Figure 2 ). Its stabilizer, of order 24, is the group of collineations of this plane that fix A A A E 0 E_0 E 0
Figure 2. The Fano plane on the parties of E 0 , … , E 5 E_0,\ldots,E_5 E 0 , … , E 5 F 7 F_7 F 7 A B C ABC A B C A D E ADE A D E A F G AFG A F G A A A
μ 0 = MMI ( B C : D E : F G ) , μ 1 = MMI ( B : D : F ) , μ 2 = MMI ( A : C : D F ) + MMI ( A : E : B F ) + MMI ( A : G : B D ) , μ 3 = MMI ( A : B : D ) + MMI ( A : B : F ) + MMI ( A : D : F ) , μ 4 = MMI ( B : E : G ) + MMI ( C : D : G ) + MMI ( C : E : F ) , (20) \begin{aligned}
\mu_0&=\operatorname{MMI}(BC:DE:FG),\qquad\mu_1=\operatorname{MMI}(B:D:F),\\
\mu_2&=\operatorname{MMI}(A:C:DF)+\operatorname{MMI}(A:E:BF)+\operatorname{MMI}(A:G:BD),\\
\mu_3&=\operatorname{MMI}(A:B:D)+\operatorname{MMI}(A:B:F)+\operatorname{MMI}(A:D:F),\\
\mu_4&=\operatorname{MMI}(B:E:G)+\operatorname{MMI}(C:D:G)+\operatorname{MMI}(C:E:F), \tag*{(20)}
\end{aligned} μ 0 μ 2 μ 3 μ 4 = MMI ( B C : D E : F G ) , μ 1 = MMI ( B : D : F ) , = MMI ( A : C : D F ) + MMI ( A : E : B F ) + MMI ( A : G : B D ) , = MMI ( A : B : D ) + MMI ( A : B : F ) + MMI ( A : D : F ) , = MMI ( B : E : G ) + MMI ( C : D : G ) + MMI ( C : E : F ) , (20) and define
E 1 = E 0 − 2 μ 0 , E 2 = E 1 − 2 μ 1 , E 3 = E 2 − μ 2 , E 4 = E 3 − μ 3 , E 5 = E 4 − 2 μ 4 . (21) E_1=E_0-2\mu_0,\qquad E_2=E_1-2\mu_1,\qquad E_3=E_2-\mu_2,\qquad E_4=E_3-\mu_3,\qquad E_5=E_4-2\mu_4 . \tag*{(21)} E 1 = E 0 − 2 μ 0 , E 2 = E 1 − 2 μ 1 , E 3 = E 2 − μ 2 , E 4 = E 3 − μ 3 , E 5 = E 4 − 2 μ 4 . (21) The first step gives E 1 E_1 E 1 E 0 E_0 E 0 A A A A A A A A A E 1 , … , E 5 E_1,\ldots,E_5 E 1 , … , E 5
Theorem 4.11. The inequalities Q 8 Q_8 Q 8 Q 8 ′ Q'_8 Q 8 ′ Q 8 ′ ′ Q''_8 Q 8 ′′ N = 8 N = 8 N = 8 E 0 , … , E 5 E_0,\ldots,E_5 E 0 , … , E 5 N = 7 N = 7 N = 7
Proof. Superbalance is an exact integer computation of all Bell values. Validity of Q 8 Q_8 Q 8 Q 8 ′ Q'_8 Q 8 ′ Q 8 ′ ′ Q''_8 Q 8 ′′ { 0 , 1 } 14 \{0,1\}^{14} { 0 , 1 } 14 Lemma 2.12 ), through Lemma 2.13 or the theorem of Bao et al. applied to M Q 8 MQ_8 M Q 8 M Q 8 ′ MQ'_8 M Q 8 ′ M Q 8 ′ ′ MQ''_8 M Q 8 ′′ M M M E 0 E_0 E 0 Q 8 ′ Q'_8 Q 8 ′ E 1 , … , E 5 E_1,\ldots,E_5 E 1 , … , E 5 Lemma 2.13 gives validity. For E 0 E_0 E 0 E 1 E_1 E 1 E 3 E_3 E 3 E 4 E_4 E 4 Lemma 2.13 and without the deletion, from the integer maps for 2 E 0 2E_0 2 E 0 2 E 1 2E_1 2 E 1 2 E 3 2E_3 2 E 3 2 E 4 2E_4 2 E 4 Proposition 6.1 , by the theorem of Bao et al. (§ 2.3 ).
For the non-existence, in each of the nine inequalities the seven LHS terms that contain A A A U \mathcal{U} U 2 7 2^7 2 7 [ 0 , x ( A ) ] [0,x^{(A)}] [ 0 , x ( A ) ] Lemma 2.15 it suffices to show that the integer map problem on U \mathcal{U} U ∣ U ∣ = 135 |\mathcal{U}| = 135 ∣ U ∣ = 135 N = 8 N = 8 N = 8 ∣ U ∣ = 134 |\mathcal{U}| = 134 ∣ U ∣ = 134 N = 7 N = 7 N = 7 drat-trim (Table 4 ). □
By § 2.3 , Theorem 4.11 also excludes unscaled maps on the full cube in the fully split presentation and in the presentations with merged right-hand side.
Proposition 4.12 (The descent). E 0 = E 5 + 2 μ 0 + 2 μ 1 + μ 2 + μ 3 + 2 μ 4 E_0 = E_5 + 2\mu_0 + 2\mu_1 + \mu_2 + \mu_3 + 2\mu_4 E 0 = E 5 + 2 μ 0 + 2 μ 1 + μ 2 + μ 3 + 2 μ 4 μ 0 \mu_0 μ 0 μ 1 \mu_1 μ 1 μ 4 \mu_4 μ 4 maximal : sup { t : E s − t μ s valid } = 2 \sup\{t: E_s - t\mu_s\ \text{valid}\} = 2 sup { t : E s − t μ s valid } = 2 s = 0 , 1 , 4 s = 0,1,4 s = 0 , 1 , 4
The identities (4.10) are exact integer identities, the lower bounds 2 follow from the validity of the next inequality (Theorem 4.11 ), and the upper bounds from the graph models listed in Table 4 . None of Q 8 Q_8 Q 8 Q 8 ′ Q'_8 Q 8 ′ E 0 , … , E 5 E_0,\ldots,E_5 E 0 , … , E 5 Q 8 Q_8 Q 8 Q 8 ′ Q'_8 Q 8 ′ E 0 , … , E 4 E_0,\ldots,E_4 E 0 , … , E 4 6 E 5 = 2 X 7 + Y 7 + 3 μ 5 6E_5 = 2X_7 + Y_7 + 3\mu_5 6 E 5 = 2 X 7 + Y 7 + 3 μ 5 μ 5 \mu_5 μ 5 X 7 X_7 X 7 § 1 , and Y 7 Y_7 Y 7 Proposition 5.4 . Whether Q 8 ′ ′ Q''_8 Q 8 ′′ 8 _8 8 [6 ] . § 5 follows the chain one step further, to a facet.
A superbalanced facet of HEC7 and its unscaled map
In § 4 the failure of unscaled maps survived five splittings of E 0 E_0 E 0 6 E 5 = 2 X 7 + Y 7 + 3 μ 5 6E_5 = 2X_7 + Y_7 + 3\mu_5 6 E 5 = 2 X 7 + Y 7 + 3 μ 5 X 7 X_7 X 7 Y 7 Y_7 Y 7
caption: tbl:1 . The superbalanced inequalities of Theorem 4.11. L L L R R R ∣ A ∣ |\mathcal{A}| ∣ A ∣ N = 7 N=7 N = 7 2 Q 2Q 2 Q sup { t : Q − t X valid } \sup\{t: Q-tX\ \text{valid}\} sup { t : Q − tX valid } X X X ≥ c \ge c ≥ c X X X
:::
this identity. In this section we split Y 7 Y_7 Y 7 F 7 F_7 F 7 H E C 7 \mathrm{HEC}_7 HEC 7 E 0 E_0 E 0 F 7 F_7 F 7 F 7 F_7 F 7
The inequality F 7 F_7 F 7
Let N = 7 N=7 N = 7 A , … , G A,\ldots,G A , … , G
F 7 : 2 A B C + 2 A D E + 2 A F G + B D F + 4 B D G + 4 B E F + B E G + 4 C D F + C D G + C E F + 2 A B D F + 2 A B E G + 2 A C D G + 2 A C E F + B C D E + B C F G + D E F G + 2 B C D E G + 2 B C E F G + 2 C D E F G ≥ 3 B + 2 C + 3 D + 2 E + 3 F + 2 G + 2 A B + 2 A D + 2 A F + 3 B E + 3 B G + 3 C D + 3 C F + 3 D G + 3 E F + A B D G + A B E F + A C D F + 3 A C E G + B C D E F + B C D F G + B D E F G + 4 B C D E F G + 2 A B C D E F G (22) \begin{aligned}
F_7:\quad&2ABC+2ADE+2AFG+BDF+4BDG+4BEF+BEG+4CDF\\
&+CDG+CEF+2ABDF+2ABEG+2ACDG+2ACEF+BCDE\\
&+BCFG+DEFG+2BCDEG+2BCEFG+2CDEFG\\
&\ge3B+2C+3D+2E+3F+2G+2AB+2AD+2AF+3BE+3BG\\
&\quad+3CD+3CF+3DG+3EF+ABDG+ABEF+ACDF+3ACEG\\
&\quad+BCDEF+BCDFG+BDEFG+4BCDEFG+2ABCDEFG \tag*{(22)}
\end{aligned} F 7 : 2 A B C + 2 A D E + 2 A F G + B D F + 4 B D G + 4 B E F + B E G + 4 C D F + C D G + C E F + 2 A B D F + 2 A B E G + 2 A C D G + 2 A C E F + B C D E + B C F G + D E F G + 2 B C D E G + 2 B C E F G + 2 C D E F G ≥ 3 B + 2 C + 3 D + 2 E + 3 F + 2 G + 2 A B + 2 A D + 2 A F + 3 B E + 3 B G + 3 C D + 3 C F + 3 D G + 3 E F + A B D G + A B E F + A C D F + 3 A C E G + B C D E F + B C D F G + B D E F G + 4 B C D E F G + 2 A B C D E F G (22) has L = 20 L=20 L = 20 R = 24 R=24 R = 24 ∣ α ∣ = 39 |\alpha|=39 ∣ α ∣ = 39 ∣ β ∣ = 54 |\beta|=54 ∣ β ∣ = 54 F 7 F_7 F 7 A A A E 0 E_0 E 0 A A A Figure 2 and the complements of the four lines that miss A A A A ( F 7 ) \mathcal{A}(F_7) A ( F 7 ) 2 20 2^{20} 2 20
The stabilizer Stab ( F 7 ) \operatorname{Stab}(F_7) Stab ( F 7 ) A A A ( B , C ) (B,C) ( B , C ) ( D , E ) (D,E) ( D , E ) ( F , G ) (F,G) ( F , G ) S 3 S_3 S 3 ( B D ) ( C E ) (BD)(CE) ( B D ) ( C E ) ( B F ) ( C G ) (BF)(CG) ( B F ) ( C G ) E 0 E_0 E 0 F 7 F_7 F 7 8 ! 8! 8 ! A , … , G , O A,\ldots,G,O A , … , G , O F 7 F_7 F 7 [19 ] ), since every term of such an inequality contains both or neither of the two merged points (for a pair i , O i,O i , O i i i A , … , G , O A,\ldots,G,O A , … , G , O F 7 F_7 F 7
The facet
Theorem 5.2. The inequality F 7 F_7 F 7 H E C 7 \mathrm{HEC}_7 HEC 7 H E C 7 \mathrm{HEC}_7 HEC 7
Proof. For validity, there is a map n : A ( F 7 ) → ∏ r = 1 24 [ 0 , β r ] n\colon\mathcal{A}(F_7) \to\prod_{r=1}^{24}[0,\beta_r] n : A ( F 7 ) → ∏ r = 1 24 [ 0 , β r ] A ( F 7 ) \mathcal{A}(F_7) A ( F 7 ) F 7 F_7 F 7
For the facet property, there are 126 explicit graph models with integer edge weights on which F 7 F_7 F 7 H E C 7 \mathrm{HEC}_7 HEC 7 R 127 \mathbb{R}^{127} R 127 H E C 7 ∩ F 7 ⊥ \mathrm{HEC}_7 \cap F_7^\perp HEC 7 ∩ F 7 ⊥ 126 = 2 7 − 2 126=2^7-2 126 = 2 7 − 2 F 7 F_7 F 7
Lemma 2.13 keeps the validity certificate small, since the map needs values only on A ( F 7 ) \mathcal{A}(F_7) A ( F 7 ) 2 20 2^{20} 2 20
Remark 5.3 (Comparison with the literature). The facet F 7 F_7 F 7 Table 6 (Appendix C.3): none of them has the canonical form of F 7 F_7 F 7 8 ! 8! 8 ! F 7 F_7 F 7 F 7 F_7 F 7 H E C 7 \mathrm{HEC}_7 HEC 7
Table 6. The 43 seven-party inequalities with which F 7 F_7 F 7
Where F7 comes from
The facet arises from the chain of Section 4 by one more splitting, with a sum of other valid inequalities in the role of X X X g = ( D F ) ( E G ) g=(DF)(EG) g = ( D F ) ( E G ) F 7 F_7 F 7 X 7 X_7 X 7 Y 7 Y_7 Y 7 V 7 V_7 V 7 X 7 X_7 X 7 V 7 V_7 V 7 V 7 ′ V_7' V 7 ′ μ 5 \mu_5 μ 5 Y 7 = 6 E 5 − 2 X 7 − 3 μ 5 Y_7=6E_5-2X_7-3\mu_5 Y 7 = 6 E 5 − 2 X 7 − 3 μ 5
Proposition 5.4. The identities
4 Y 7 = 3 F 7 + 2 V 7 + g ( V 7 ) + 2 V 7 ′ (23) 4Y_7=3F_7+2V_7+g(V_7)+2V_7' \tag*{(23)} 4 Y 7 = 3 F 7 + 2 V 7 + g ( V 7 ) + 2 V 7 ′ (23) and
24 E 0 = 3 F 7 + 2 V 7 + g ( V 7 ) + 2 V 7 ′ + 8 X 7 + 12 μ 5 + 48 μ 4 + 24 μ 3 + 24 μ 2 + 48 μ 1 + 48 μ 0 (24) 24E_0=3F_7+2V_7+g(V_7)+2V_7'+8X_7+12\mu_5+48\mu_4+24\mu_3+24\mu_2+48\mu_1+48\mu_0 \tag*{(24)} 24 E 0 = 3 F 7 + 2 V 7 + g ( V 7 ) + 2 V 7 ′ + 8 X 7 + 12 μ 5 + 48 μ 4 + 24 μ 3 + 24 μ 2 + 48 μ 1 + 48 μ 0 (24) hold exactly, and every inequality on their right-hand sides is valid. Consequently every graph model on which E 0 E_0 E 0 F 7 ⋅ S = 0 F_7\cdot S=0 F 7 ⋅ S = 0 H E C 7 ∩ E 0 ⊥ \mathrm{HEC}_7\cap E_0^\perp HEC 7 ∩ E 0 ⊥ H E C 7 ∩ F 7 ⊥ \mathrm{HEC}_7\cap F_7^\perp HEC 7 ∩ F 7 ⊥ E 0 E_0 E 0 E 1 , … , E 5 E_1,\ldots,E_5 E 1 , … , E 5 Y 7 Y_7 Y 7
Proof. The identity (5.5) is an identity of integer vectors in Z 127 \mathbb{Z}^{127} Z 127 6 E 5 = 2 X 7 + Y 7 + 3 μ 5 6E_5=2X_7+Y_7+3\mu_5 6 E 5 = 2 X 7 + Y 7 + 3 μ 5 Y 7 Y_7 Y 7 24 E 5 = 8 X 7 + 4 Y 7 + 12 μ 5 = 3 F 7 + 2 V 7 + g ( V 7 ) + 2 V 7 ′ + 8 X 7 + 12 μ 5 24E_5=8X_7+4Y_7+12\mu_5=3F_7+2V_7+g(V_7)+2V_7'+8X_7+12\mu_5 24 E 5 = 8 X 7 + 4 Y 7 + 12 μ 5 = 3 F 7 + 2 V 7 + g ( V 7 ) + 2 V 7 ′ + 8 X 7 + 12 μ 5 E 0 = E 5 + 2 μ 0 + 2 μ 1 + μ 2 + μ 3 + 2 μ 4 E_0=E_5+2\mu_0+2\mu_1+\mu_2+\mu_3+2\mu_4 E 0 = E 5 + 2 μ 0 + 2 μ 1 + μ 2 + μ 3 + 2 μ 4 F 7 F_7 F 7 V 7 V_7 V 7 V 7 ′ V_7' V 7 ′ X 7 X_7 X 7 Table 4 ). The relabeling g ( V 7 ) g(V_7) g ( V 7 ) H E C 7 \mathrm{HEC}_7 HEC 7 μ s \mu_s μ s [4 ] , and Y 7 Y_7 Y 7
For a graph model with entropy vector S S S S S S E 0 ⋅ S = 0 E_0\cdot S=0 E 0 ⋅ S = 0 3 F 7 ⋅ S = 0 3F_7\cdot S=0 3 F 7 ⋅ S = 0 E s E_s E s 1 ≤ s ≤ 5 1\leq s\leq5 1 ≤ s ≤ 5 24 E s = 24 E 5 + ( 24E_s=24E_5+( 24 E s = 24 E 5 + ( μ 0 , … , μ 4 \mu_0,\ldots,\mu_4 μ 0 , … , μ 4 Y 7 Y_7 Y 7
Among the summands of (5.6), F 7 F_7 F 7 Table 2 ).
Table 2. The inequalities in (5.5) and (5.6) other than the sums of MMI instances, and the inequality P 7 P_7 P 7 A \mathcal{A} A 7 _7 7
Unscaled maps of F 7 F_7 F 7
Theorem 5.7. (i) F 7 F_7 F 7 A ( F 7 ) \mathcal{A}(F_7) A ( F 7 ) F 7 F_7 F 7 k min A ( F 7 ) = 1 k_{\min}^{\mathcal{A}}(F_7)=1 k m i n A ( F 7 ) = 1
(ii) No integer map for F 7 F_7 F 7 A ( F 7 ) \mathcal{A}(F_7) A ( F 7 ) Stab ( F 7 ) \operatorname{Stab}(F_7) Stab ( F 7 )
Proof. (i) The certificate is a table of integers n r ( u ) ∈ { 0 , … , β r } n_r(u)\in\{0,\ldots,\beta_r\} n r ( u ) ∈ { 0 , … , β r } u ∈ A ( F 7 ) u\in\mathcal{A}(F_7) u ∈ A ( F 7 ) A ( F 7 ) \mathcal{A}(F_7) A ( F 7 ) Definition 2.11 , verify that it is the set of points of the certificate, and verify the pins, the ranges and the contraction condition on all pairs of points in exact arithmetic (Appendix § 8 .§ 2 ). An integer map is a real map, so Lemma 2.13 applies.
(ii) The equivariant encoding of Appendix § 8 .§ 4 , in which the variables of ( u , r ) (u,r) ( u , r ) ( g ⋅ u , g ( r ) ) (g\cdot u,g(r)) ( g ⋅ u , g ( r )) g ∈ Stab ( F 7 ) g\in\operatorname{Stab}(F_7) g ∈ Stab ( F 7 ) drat-trim. Every equivariant integer map would give a satisfying assignment. □
The inequality F 7 F_7 F 7 k min A = 1 k_{\min}^{\mathcal{A}}=1 k m i n A = 1 § 2.4 ) asks about, while the inequalities of Theorem 4.11 do not. The obstruction in (ii) is one of integrality. Averaging an integer map of (i) over the six elements of Stab ( F 7 ) \operatorname{Stab}(F_7) Stab ( F 7 ) 1 6 Z \frac{1}{6}\mathbb{Z} 6 1 Z 6 F 7 6F_7 6 F 7 k k k k F 7 kF_7 k F 7 A ( F 7 ) \mathcal{A}(F_7) A ( F 7 )
We did not attempt to construct an integer map for F 7 F_7 F 7 { 0 , 1 } 20 \{0,1\}^{20} { 0 , 1 } 20 k min ( F 7 ) = 1 k_{\min}(F_7)=1 k m i n ( F 7 ) = 1 Lemma 2.15 cannot exclude it, because the map of (i) restricts to U ( F 7 ) ⊆ A ( F 7 ) U(F_7)\subseteq\mathcal{A}(F_7) U ( F 7 ) ⊆ A ( F 7 )
Remark 5.8 (The other summands). The inequalities V 7 V_7 V 7 V 7 ′ V'_7 V 7 ′ Theorem 5.7 (i). As for F 7 F_7 F 7 V 7 V_7 V 7 A ( V 7 ) \mathcal{A}(V_7) A ( V 7 ) ( B F ) ( C G ) (BF)(CG) ( B F ) ( C G ) V 7 ′ V'_7 V 7 ′ V 7 V_7 V 7 V 7 ′ V'_7 V 7 ′ V 7 V_7 V 7 F 7 ⊥ F_7^\perp F 7 ⊥ V 7 ⊥ ∩ F 7 ⊥ V_7^\perp\cap F_7^\perp V 7 ⊥ ∩ F 7 ⊥ V 7 V_7 V 7 V 7 ⋅ S = 0 V_7\cdot S=0 V 7 ⋅ S = 0 F 7 ⋅ S > 0 F_7\cdot S>0 F 7 ⋅ S > 0 X 7 X_7 X 7 Y 7 Y_7 Y 7 (24) writes 24 E 0 24E_0 24 E 0 X 7 X_7 X 7 F 7 F_7 F 7 V 7 V_7 V 7 g ( V 7 ) g(V_7) g ( V 7 ) V 7 ′ V'_7 V 7 ′ [6 ] . Remark 5.9 writes E 0 E_0 E 0 X 7 X_7 X 7
Remark 5.9 (A half-sum behind the failures). The seven-party superb alanced inequality P 7 P_7 P 7 § 1 has an integer map on its realizable domain, of 6,912 points, certified like the map of Theorem 5.7 (i), and is therefore valid by Lemma 2.13 . With g = ( D F ) ( E G ) g=(DF)(EG) g = ( D F ) ( E G )
2 X 7 = V 7 ′ + P 7 + 2 g ( P 7 ) , 2 E 5 = V 7 ′ + P 7 + 2 MMI ( D : B G : C F ) + 2 MMI ( E : B F : C G ) (25) 2X_7=V'_7+P_7+2g(P_7),\qquad2E_5=V'_7+P_7+2\operatorname{MMI}(D:BG:CF)+2\operatorname{MMI}(E:BF:CG) \tag*{(25)} 2 X 7 = V 7 ′ + P 7 + 2 g ( P 7 ) , 2 E 5 = V 7 ′ + P 7 + 2 MMI ( D : B G : C F ) + 2 MMI ( E : B F : C G ) (25) hold exactly, and with (21) the second gives 2 E s = V 7 ′ + P 7 + 2 M s 2E_s=V'_7+P_7+2M_s 2 E s = V 7 ′ + P 7 + 2 M s s = 0 , … , 5 s=0,\ldots,5 s = 0 , … , 5 M s M_s M s MMI ( D : B G : C F ) + MMI ( E : B F : C G ) \operatorname{MMI}(D:BG:CF)+\operatorname{MMI}(E:BF:CG) MMI ( D : B G : C F ) + MMI ( E : B F : C G ) μ s , … , μ 4 \mu_s,\ldots,\mu_4 μ s , … , μ 4 X 7 X_7 X 7 E s E_s E s V 7 ′ V'_7 V 7 ′ P 7 P_7 P 7 g ( P 7 ) g(P_7) g ( P 7 ) 1 2 ( V 7 ′ + P 7 ) \frac{1}{2}(V'_7+P_7) 2 1 ( V 7 ′ + P 7 ) A A A E 0 E_0 E 0 U \mathcal{U} U Lemma 2.15 ). So in these decompositions the coefficients 1 2 \frac{1}{2} 2 1 V 7 ′ V'_7 V 7 ′ P 7 P_7 P 7
In the one case where we followed a superbalanced inequality without unscaled maps down to a facet, the facet has an unscaled contraction proof on its realizable domain, and every such proof breaks its symmetry. The inequality X 7 X_7 X 7 (25) it is a positive combination of valid inequalities that are not multiples of it. If V 7 V_7 V 7 V 7 ′ V'_7 V 7 ′ P 7 P_7 P 7
How much scaling is needed
In this section we ask how large the least scaling k min k_{\min} k m i n [20 ] concerns every valid inequality and allows a uniform rescaling before a map is sought, so the question applies to every valid inequality, balanced or not. Star inequalities are the class in which we can answer it exactly; since they are implied by subadditivity and are not balanced (§ 6.5 ), they show how large the rescaling allowed by that claim may need to be for valid inequalities, and they say nothing about the scaling needed by the balanced and superbalanced inequalities of § 3 and § 4 . We first record what we know for the superbalanced inequalities of § 4 . We then show that for star inequalities k min k_{\min} k m i n k k k 1 k Z m \frac{1}{k}\mathbb{Z}^m k 1 Z m k min = 2 ( N + 1 ) / 4 k_{\min}=2^{(N+1)/4} k m i n = 2 ( N + 1 ) /4 N N N
Scaled maps of the superbalanced failures
For the inequalities of Theorem 4.11 we can decide the following scaled cases.
Proposition 6.1. (i) 3 Q 8 3Q_8 3 Q 8
(ii) 2 E 0 2E_0 2 E 0 2 E 1 2E_1 2 E 1 2 E 3 2E_3 2 E 3 2 E 4 2E_4 2 E 4 k min ( E s ) = k min A ( E s ) = 2 k_{\min}(E_s)=k^A_{\min}(E_s)=2 k m i n ( E s ) = k m i n A ( E s ) = 2 s = 0 , 1 , 3 , 4 s=0,1,3,4 s = 0 , 1 , 3 , 4
Part (i) is certified like Theorem 4.11 , by a DRAT proof for the problem for 3 Q 8 3Q_8 3 Q 8 U \mathcal{U} U { 0 , 1 } 14 \{0,1\}^{14} { 0 , 1 } 14 E 0 E_0 E 0 E 1 E_1 E 1 { 0 , 1 } 15 \{0,1\}^{15} { 0 , 1 } 15 E 3 E_3 E 3 E 4 E_4 E 4 Lemma 2.12 , and by at least one of them also on all 134,209,536 or 536,854,528 pairs of points of { 0 , 1 } 14 \{0,1\}^{14} { 0 , 1 } 14 { 0 , 1 } 15 \{0,1\}^{15} { 0 , 1 } 15 § 8 .§ 2 ). So k min A ( E s ) ≤ k min ( E s ) ≤ 2 k^A_{\min}(E_s)\leq k_{\min}(E_s)\leq2 k m i n A ( E s ) ≤ k m i n ( E s ) ≤ 2 Theorem 4.11 excludes k = 1 k=1 k = 1 2 E 0 2E_0 2 E 0 2 E 1 2E_1 2 E 1 μ 0 \mu_0 μ 0 2 E 0 = 2 E 1 + 4 μ 0 2E_0 = 2E_1 + 4\mu_0 2 E 0 = 2 E 1 + 4 μ 0 μ 0 \mu_0 μ 0 E 1 E_1 E 1 A ( E 4 ) \mathcal{A}(E_4) A ( E 4 ) 2 E 4 2E_4 2 E 4 Stab ( E 4 ) \operatorname{Stab}(E_4) Stab ( E 4 ) § 8 .§ 4 ), checked in exact arithmetic on all 4,250,070 pairs of points. The least scaling of E 2 E_2 E 2 E 5 E_5 E 5 Q 8 Q_8 Q 8 Q 8 ′ Q'_8 Q 8 ′ Q 8 ′ ′ Q''_8 Q 8 ′′
Star inequalities and their scaling spectrum
Definition 6.2 (Star inequalities). Let m ≥ 1 m \ge1 m ≥ 1 J 1 , … , J m ⊆ [ N ] J_1,\ldots,J_m \subseteq[N] J 1 , … , J m ⊆ [ N ] 2 ≤ ∣ J K ∣ ≤ N − 1 2 \le|J_K| \le N-1 2 ≤ ∣ J K ∣ ≤ N − 1 β 1 , … , β m \beta_1,\ldots,\beta_m β 1 , … , β m ρ i \rho_i ρ i i ∈ [ N ] ∪ { O } i \in[N] \cup\{O\} i ∈ [ N ] ∪ { O } radii . The star inequality with these data is
Q : ∑ i ∈ [ N ] ρ i S ( i ) + ρ O S ( [ N ] ) ≥ ∑ K = 1 m β K S ( J K ) . (26) Q:\quad\sum_{i\in[N]} \rho_i S(i) + \rho_O S([N]) \ge\sum_{K=1}^{m} \beta_K S(J_K). \tag*{(26)} Q : i ∈ [ N ] ∑ ρ i S ( i ) + ρ O S ([ N ]) ≥ K = 1 ∑ m β K S ( J K ) . (26) It has R = m R=m R = m word of a party i ∈ [ N ] i \in[N] i ∈ [ N ] η ( i ) = ( β K [ i ∈ J K ] ) K = 1 m \eta^{(i)} = (\beta_K [i \in J_K])_{K=1}^{m} η ( i ) = ( β K [ i ∈ J K ] ) K = 1 m η ( O ) = 0 \eta^{(O)}=0 η ( O ) = 0 star polytope of Q Q Q
Π ( Q ) = { c ∈ ∏ K = 1 m [ 0 , β K ] : ∥ c − η ( i ) ∥ 1 ≤ ρ i for all i ∈ [ N ] ∪ { O } } . (27) \Pi(Q)=\left\{c\in\prod_{K=1}^{m}[0,\beta_K]:\|c-\eta^{(i)}\|_1\le\rho_i\text{ for all }i\in[N]\cup\{O\}\right\}. \tag*{(27)} Π ( Q ) = { c ∈ K = 1 ∏ m [ 0 , β K ] : ∥ c − η ( i ) ∥ 1 ≤ ρ i for all i ∈ [ N ] ∪ { O } } . (27) Since S ( [ N ] ) = S ( O ) S([N])=S(O) S ([ N ]) = S ( O ) N + 1 N+1 N + 1 Q Q Q Π ( Q ) \Pi(Q) Π ( Q ) ℓ 1 \ell_1 ℓ 1 ρ i \rho_i ρ i η ( i ) \eta^{(i)} η ( i ) i i i
Lemma 6.5 (Linearity on the box). Let η ∈ ∏ K { 0 , β K } \eta\in\prod_K\{0,\beta_K\} η ∈ ∏ K { 0 , β K } c ∈ ∏ K [ 0 , β K ] c\in\prod_K[0,\beta_K] c ∈ ∏ K [ 0 , β K ]
∥ c − η ∥ 1 = ∑ K : η K = 0 c K + ∑ K : η K = β K ( β K − c K ) , (28) \|c-\eta\|_1=\sum_{K:\eta_K=0}c_K+\sum_{K:\eta_K=\beta_K}(\beta_K-c_K), \tag*{(28)} ∥ c − η ∥ 1 = K : η K = 0 ∑ c K + K : η K = β K ∑ ( β K − c K ) , (28) and ∥ c − η ∥ 1 + ∥ c − η ˉ ∥ 1 = ∣ β ∣ \|c-\eta\|_1+\|c-\bar{\eta}\|_1=|\beta| ∥ c − η ∥ 1 + ∥ c − η ˉ ∥ 1 = ∣ β ∣ η ˉ = β − η \bar{\eta}=\beta-\eta η ˉ = β − η Π ( Q ) \Pi(Q) Π ( Q ) N + 1 N+1 N + 1 ± 1 \pm1 ± 1 Q Q Q ∣ β ∣ |\beta| ∣ β ∣ Π ( Q ) \Pi(Q) Π ( Q )
The proof is in Appendix B.8.
Validity of a star inequality follows from subadditivity once its polytope has a point. For each K K K
S A K 1 : ∑ i ∈ J K S ( i ) ≥ S ( J K ) , S A K 2 : ∑ i ∈ [ N ] ∖ J K S ( i ) + S ( [ N ] ) ≥ S ( J K ) , (29) \mathrm{SA}^{1}_{K}:\quad\sum_{i\in J_K}S(i)\ge S(J_K),\qquad\mathrm{SA}^{2}_{K}:\quad\sum_{i\in[N]\setminus J_K}S(i)+S([N])\ge S(J_K), \tag*{(29)} SA K 1 : i ∈ J K ∑ S ( i ) ≥ S ( J K ) , SA K 2 : i ∈ [ N ] ∖ J K ∑ S ( i ) + S ([ N ]) ≥ S ( J K ) , (29) where the second is subadditivity for the parties ( [ N ] ∖ J K ) ∪ { O } ([N]\setminus J_K)\cup\{O\} ([ N ] ∖ J K ) ∪ { O } S ( J K ) S(J_K) S ( J K ) H E C N \mathrm{HEC}_N HEC N [31 ] . We use the same symbols for their coefficient vectors and write P I P_I P I S ( I ) ≥ 0 S(I)\ge0 S ( I ) ≥ 0
Lemma 6.8 (Validity from a real point). If c ∈ Π ( Q ) c\in\Pi(Q) c ∈ Π ( Q )
Q = ∑ K = 1 m [ ( β K − c K ) S A K 1 + c K S A K 2 ] + ∑ i ∈ [ N ] ( ρ i − ∥ c − η ( i ) ∥ 1 ) P { i } + ( ρ O − ∥ c ∥ 1 ) P [ N ] . (30) Q=\sum_{K=1}^{m}\left[(\beta_K-c_K)\mathrm{SA}^{1}_{K}+c_K\mathrm{SA}^{2}_{K}\right]+\sum_{i\in[N]}\left(\rho_i-\|c-\eta^{(i)}\|_1\right)P_{\{i\}}+\left(\rho_O-\|c\|_1\right)P_{[N]}. \tag*{(30)} Q = K = 1 ∑ m [ ( β K − c K ) SA K 1 + c K SA K 2 ] + i ∈ [ N ] ∑ ( ρ i − ∥ c − η ( i ) ∥ 1 ) P { i } + ( ρ O − ∥ c ∥ 1 ) P [ N ] . (30) with all coefficients nonnegative. In particular Q Q Q k c ∈ Z m kc\in\mathbb{Z}^m k c ∈ Z m k Q kQ k Q
The proof, a comparison of coefficients, is in Appendix B.8.
Theorem 6.10 (Scaling spectrum of star inequalities). Let Q Q Q k ≥ 1 k \ge1 k ≥ 1 k Q kQ k Q Π ( Q ) ∩ 1 k Z m ≠ ∅ \Pi(Q) \cap\frac{1}{k}\mathbb{Z}^{m} \ne\varnothing Π ( Q ) ∩ k 1 Z m = ∅ Π ( Q ) ≠ ∅ \Pi(Q) \ne\varnothing Π ( Q ) = ∅ Q Q Q
k min ( Q ) = min { k ≥ 1 : Π ( Q ) ∩ 1 k Z m ≠ ∅ } < ∞ , (31) k_{\min}(Q)=\min\left\{k\ge1:\Pi(Q)\cap\frac{1}{k}\mathbb{Z}^{m}\ne\varnothing\right\}<\infty, \tag*{(31)} k m i n ( Q ) = min { k ≥ 1 : Π ( Q ) ∩ k 1 Z m = ∅ } < ∞ , (31) and if Π ( Q ) = ∅ \Pi(Q)=\varnothing Π ( Q ) = ∅ k Q kQ k Q
The proof is in Appendix B.§ 4 . The occurrence word of a party i i i S ( i ) S(i) S ( i ) S ( [ N ] ) S([N]) S ([ N ]) z z z S ( [ N ] ) S([N]) S ([ N ]) ρ i \rho_i ρ i ρ O \rho_O ρ O 0 0 0 n n n k Q kQ k Q n ( z ) / k n(z)/k n ( z ) / k Π ( Q ) \Pi(Q) Π ( Q ) c c c J K J_K J K k ( β K − c K ) k(\beta_K-c_K) k ( β K − c K ) S A K 1 \mathrm{SA}^{1}_K SA K 1 k c K kc_K k c K S A K 2 \mathrm{SA}^{2}_K SA K 2
The smallest example is the three-party star inequality
Q ′ : A + B + C + A B C ≥ A B + A C , (32) Q' :\quad A+B+C+ABC\ge AB+AC, \tag*{(32)} Q ′ : A + B + C + A B C ≥ A B + A C , (32) with all radii 1 1 1 ( 1 , 1 ) (1,1) ( 1 , 1 ) ( 1 , 0 ) (1,0) ( 1 , 0 ) ( 0 , 1 ) (0,1) ( 0 , 1 ) 0 0 0 A A A B B B C C C O O O ( A B , A C ) (AB,AC) ( A B , A C ) A , O A,O A , O B , C B,C B , C ∣ β ∣ = 2 |\beta|=2 ∣ β ∣ = 2 Lemma 6.5 every c ∈ Π ( Q ′ ) c\in\Pi(Q') c ∈ Π ( Q ′ ) c 1 + c 2 = 1 c_1+c_2=1 c 1 + c 2 = 1 c 1 = c 2 c_1=c_2 c 1 = c 2 Π ( Q ′ ) = { ( 1 2 , 1 2 ) } \Pi(Q')=\{(\frac{1}{2},\frac{1}{2})\} Π ( Q ′ ) = {( 2 1 , 2 1 )} k Q ′ kQ' k Q ′ k k k k min ( Q ′ ) = 2 k_{\min}(Q')=2 k m i n ( Q ′ ) = 2 2 Q ′ 2Q' 2 Q ′ z = 0001 z=0001 z = 0001 A , B , C , A B C A,B,C,ABC A , B , C , A B C 1 1 1 n ( z ) n(z) n ( z ) ℓ 1 \ell_1 ℓ 1 k k k [ 0 , k ] 2 [0,k]^2 [ 0 , k ] 2 n ( z ) = ( k 2 , k 2 ) n(z)=(\frac{k}{2},\frac{k}{2}) n ( z ) = ( 2 k , 2 k ) Q ′ Q' Q ′
Coin weighing and single-point polytopes
To make k min k_{\min} k m i n Lemma 6.5 ), and balance conditions from coin weighing make them determine the point. We use the language of coin weighing, and the superexponential lower bound of § 6.4 rests on the ill-conditioned weighing matrices of Alon and Vũ [26 ] .
We take β = 1 \beta=1 β = 1 1 X ∈ { 0 , 1 } m \mathbf{1}_X\in\{0,1\}^{m} 1 X ∈ { 0 , 1 } m X ⊆ [ m ] X\subseteq[m] X ⊆ [ m ] 1 = 1 [ m ] \mathbf{1}=\mathbf{1}_{[m]} 1 = 1 [ m ] K ∈ [ m ] K\in[m] K ∈ [ m ] T ⊆ [ m ] T\subseteq[m] T ⊆ [ m ] T T T ξ ∈ R m \xi\in\mathbb{R}^{m} ξ ∈ R m T T T ξ ( T ) = ξ ( T ‾ ) \xi(T)=\xi(\overline{T}) ξ ( T ) = ξ ( T ) T ‾ = [ m ] ∖ T \overline{T}=[m]\setminus T T = [ m ] ∖ T ξ ( X ) = ∑ K ∈ X ξ K \xi(X)=\sum_{K\in X}\xi_K ξ ( X ) = ∑ K ∈ X ξ K § 2.2 . For ξ ∈ [ 0 , 1 ] m \xi\in[0,1]^m ξ ∈ [ 0 , 1 ] m
∥ ξ − 1 X ∥ 1 = ∑ K ∉ X ξ K + ∑ K ∈ X ( 1 − ξ K ) = ∥ ξ ∥ 1 + ∣ X ∣ − 2 ξ ( X ) , (33) \left\|\xi-\mathbf{1}_X\right\|_1=\sum_{K\notin X}\xi_K+\sum_{K\in X}(1-\xi_K)=\|\xi\|_1+|X|-2\xi(X), \tag*{(33)} ∥ ξ − 1 X ∥ 1 = K ∈ / X ∑ ξ K + K ∈ X ∑ ( 1 − ξ K ) = ∥ ξ ∥ 1 + ∣ X ∣ − 2 ξ ( X ) , (33) so a party with word 1 T \mathbf{1}_T 1 T ∣ T ∣ |T| ∣ T ∣ T T T ξ ( T ) ≥ ξ ( T ‾ ) \xi(T)\ge\xi(\overline{T}) ξ ( T ) ≥ ξ ( T )
Theorem 6.14 (Coin-weighing stars). Let m ≥ 2 m\ge2 m ≥ 2 N ≥ 3 N\ge3 N ≥ 3 T = ( T 1 , … , T N − 1 ) \mathcal{T}=(T_1,\ldots,T_{N-1}) T = ( T 1 , … , T N − 1 ) [ m ] [m] [ m ]
(W1) the vectors ξ ∈ R m \xi\in\mathbb{R}^{m} ξ ∈ R m T i T_i T i R ω \mathbb{R}\omega R ω ω ∈ Z m \omega\in\mathbb{Z}^{m} ω ∈ Z m
(W2) there are γ 1 , … , γ N − 1 > 0 \gamma_1,\ldots,\gamma_{N-1}>0 γ 1 , … , γ N − 1 > 0 ∑ i = 1 N − 1 γ i ( 1 − 2 ⋅ 1 T i ) = 0 \sum_{i=1}^{N-1}\gamma_i(1-2\cdot\mathbf{1}_{T_i})=0 ∑ i = 1 N − 1 γ i ( 1 − 2 ⋅ 1 T i ) = 0
Put q = ∑ K ω K q=\sum_K\omega_K q = ∑ K ω K Q T Q_{\mathcal{T}} Q T β = 1 \beta=1 β = 1 i ≤ N − 1 i\le N-1 i ≤ N − 1 1 T i \mathbf{1}_{T_i} 1 T i ∣ T i ∣ |T_i| ∣ T i ∣ N N N 1 \mathbf{1} 1 m − 1 m-1 m − 1 1 1 1 J K J_K J K 1 1 1 K K K
(a) Q T Q_{\mathcal{T}} Q T N N N m m m Π ( Q T ) = { ω / q } \Pi(Q_{\mathcal{T}})=\{\omega/q\} Π ( Q T ) = { ω / q }
(b) q Q T = ∑ K = 1 m [ ( q − ω K ) S A K 1 + ω K S A K 2 ] qQ_{\mathcal{T}}=\sum_{K=1}^{m}[(q-\omega_K)\mathrm{SA}^{1}_K+\omega_K\mathrm{SA}^{2}_K] q Q T = ∑ K = 1 m [( q − ω K ) SA K 1 + ω K SA K 2 ] Q T Q_{\mathcal{T}} Q T
(c) k Q T kQ_{\mathcal{T}} k Q T q q q k k k k min ( Q T ) = q k_{\min}(Q_{\mathcal{T}})=q k m i n ( Q T ) = q
The proof is in Appendix B.§ 5 . The party N N N m = ∣ β ∣ m=|\beta| m = ∣ β ∣ ξ \xi ξ Π ( Q T ) \Pi(Q_{\mathcal{T}}) Π ( Q T ) ∥ ξ ∥ 1 = 1 \lVert\xi\rVert_1=1 ∥ ξ ∥ 1 = 1 Lemma 6.5 ). The constraint of a party i ≤ N − 1 i\leq N-1 i ≤ N − 1 ξ ( T i ) ≥ ξ ( T i ‾ ) \xi(T_i)\geq\xi(\overline{T_i}) ξ ( T i ) ≥ ξ ( T i ) ξ ( T i ‾ ) − ξ ( T i ) \xi(\overline{T_i})-\xi(T_i) ξ ( T i ) − ξ ( T i ) ξ \xi ξ Π ( Q T ) \Pi(Q_{\mathcal{T}}) Π ( Q T ) γ i \gamma_i γ i Definition 6.2 on the sets J K J_K J K
Two kinds of lists satisfy (W2) with all γ i = 1 \gamma_i=1 γ i = 1 paired list consists of sets T 1 , … , T n T_1,\ldots,T_n T 1 , … , T n T ‾ 1 , … , T ‾ n \overline{T}_1,\ldots,\overline{T}_n T 1 , … , T n ( 1 − 2 ⋅ 1 T ) + ( 1 − 2 ⋅ 1 T ‾ ) = 0 (\mathbf{1}-2\cdot\mathbf{1}_T)+(\mathbf{1}-2\cdot\mathbf{1}_{\overline{T}})=0 ( 1 − 2 ⋅ 1 T ) + ( 1 − 2 ⋅ 1 T ) = 0 half-regular list every coin lies in exactly half of the sets.
The family D j D_j D j ω ( 0 ) = ( 1 , 1 , 1 , 1 ) \omega^{(0)}=(1,1,1,1) ω ( 0 ) = ( 1 , 1 , 1 , 1 )
ω ( j + 1 ) = ( ω ( j ) , q j 2 , q j 2 ) , q j = ∑ K ω K ( j ) . (34) \omega^{(j+1)}=\left(\omega^{(j)},\frac{q_j}{2},\frac{q_j}{2}\right),\qquad q_j=\sum_K\omega_K^{(j)}. \tag*{(34)} ω ( j + 1 ) = ( ω ( j ) , 2 q j , 2 q j ) , q j = K ∑ ω K ( j ) . (34) Then ω ( j ) \omega^{(j)} ω ( j ) m j = 2 j + 4 m_j=2j+4 m j = 2 j + 4 q j = 2 j + 2 q_j=2^{j+2} q j = 2 j + 2 ω 1 ( j ) = 1 \omega_1^{(j)}=1 ω 1 ( j ) = 1 j + 1 j+1 j + 1 u j = 2 j + 5 u_j=2j+5 u j = 2 j + 5 v j = 2 j + 6 v_j=2j+6 v j = 2 j + 6 T 0 = { { 1 , 2 } , { 1 , 3 } , { 1 , 4 } } \mathcal{T}_0=\{\{1,2\},\{1,3\},\{1,4\}\} T 0 = {{ 1 , 2 } , { 1 , 3 } , { 1 , 4 }} T j + 1 \mathcal{T}_{j+1} T j + 1
T ∪ { u j } ( T ∈ T j , in order ) , T 1 ( j ) ∪ { v j } , { u j , v j } , (35) T\cup\{u_j\}\ (T\in\mathcal{T}_j,\text{ in order}),\qquad T_1^{(j)}\cup\{v_j\},\qquad\{u_j,v_j\}, \tag*{(35)} T ∪ { u j } ( T ∈ T j , in order ) , T 1 ( j ) ∪ { v j } , { u j , v j } , (35) where T 1 ( j ) T_1^{(j)} T 1 ( j ) T j \mathcal{T}_j T j T j \mathcal{T}_j T j m j − 1 m_j-1 m j − 1 q j / 2 q_j/2 q j /2 D j D_j D j Q T Q_{\mathcal{T}} Q T m = m j m=m_j m = m j T \mathcal{T} T T ∈ T j T\in\mathcal{T}_j T ∈ T j T ‾ \overline{T} T N j = 2 ( m j − 1 ) + 1 = 4 j + 7 N_j=2(m_j-1)+1=4j+7 N j = 2 ( m j − 1 ) + 1 = 4 j + 7 T ∈ T j T\in\mathcal{T}_j T ∈ T j 1 T \mathbf{1}_T 1 T ∣ T ∣ |T| ∣ T ∣ 1 T ‾ \mathbf{1}_{\overline{T}} 1 T ∣ T ‾ ∣ |\overline{T}| ∣ T ∣ 1 \mathbf{1} 1 m j − 1 m_j-1 m j − 1 1 1 1
Theorem 6.17 (An explicit family). For every j ≥ 0 j\geq0 j ≥ 0
(a) D j D_j D j N j = 4 j + 7 N_j=4j+7 N j = 4 j + 7 m j = 2 j + 4 m_j=2j+4 m j = 2 j + 4 Π ( D j ) = { c ( j ) } \Pi(D_j)=\{c^{(j)}\} Π ( D j ) = { c ( j ) } c ( j ) = ω ( j ) / q j c^{(j)}=\omega^{(j)}/q_j c ( j ) = ω ( j ) / q j
(b) q j D j = ∑ K = 1 m j [ ( q j − ω K ( j ) ) S A K 1 + ω K ( j ) S A K 2 ] q_jD_j=\sum_{K=1}^{m_j}[(q_j-\omega_K^{(j)})\mathrm{SA}_K^1+\omega_K^{(j)}\mathrm{SA}_K^2] q j D j = ∑ K = 1 m j [( q j − ω K ( j ) ) SA K 1 + ω K ( j ) SA K 2 ] D j D_j D j
(c) k D j kD_j k D j 2 j + 2 2^{j+2} 2 j + 2 k k k k min ( D j ) = 2 j + 2 = 2 ( N j + 1 ) / 4 k_{\min}(D_j)=2^{j+2}=2^{(N_j+1)/4} k m i n ( D j ) = 2 j + 2 = 2 ( N j + 1 ) /4
The proof is in Appendix B.§ 6 . Condition (W2) holds because the list is paired, and a vector balances T ‾ \overline{T} T T T T ξ ( T ) = ξ ( T ‾ ) \xi(T)=\xi(\overline{T}) ξ ( T ) = ξ ( T ) T ∈ T j T\in\mathcal{T}_j T ∈ T j ξ = ω ( j ) \xi=\omega^{(j)} ξ = ω ( j ) Theorem 6.14 with q = q j q=q_j q = q j j = 0 , 1 , 2 j=0,1,2 j = 0 , 1 , 2
For j = 0 j=0 j = 0 1 12 \mathbf{1}_{12} 1 12 1 34 \mathbf{1}_{34} 1 34 1 13 \mathbf{1}_{13} 1 13 1 24 \mathbf{1}_{24} 1 24 1 14 \mathbf{1}_{14} 1 14 1 23 \mathbf{1}_{23} 1 23 1 \mathbf{1} 1 1 12 = 1 { 1 , 2 } \mathbf{1}_{12}=\mathbf{1}_{\{1,2\}} 1 12 = 1 { 1 , 2 } A , … , G A,\ldots,G A , … , G
D 0 : 2 A + 2 B + 2 C + 2 D + 2 E + 2 F + 3 G + A B C D E F G ≥ A C E G + A D E G + B C E G + B D E G , (36) D_0:\qquad2A+2B+2C+2D+2E+2F+3G+ABCDEFG\geq ACEG+ADEG+BCEG+BDEG, \tag*{(36)} D 0 : 2 A + 2 B + 2 C + 2 D + 2 E + 2 F + 3 G + A B C D E F G ≥ A C E G + A D E G + B C E G + B D E G , (36) with the RHS terms in the order of the coins. Here Π ( D 0 ) = { 1 4 ( 1 , 1 , 1 , 1 ) } \Pi(D_0)=\{\frac{1}{4}(1,1,1,1)\} Π ( D 0 ) = { 4 1 ( 1 , 1 , 1 , 1 )} k D 0 kD_0 k D 0 k 4 ( 1 , 1 , 1 , 1 ) \frac{k}{4}(1,1,1,1) 4 k ( 1 , 1 , 1 , 1 ) z z z 4 D 0 = ∑ K = 1 4 ( 3 S A K 1 + S A K 2 ) 4D_0=\sum_{K=1}^{4}(3\mathrm{SA}_K^1+\mathrm{SA}_K^2) 4 D 0 = ∑ K = 1 4 ( 3 SA K 1 + SA K 2 ) Table 3 lists the certificates for D 0 D_0 D 0 D 1 D_1 D 1 D 0 D_0 D 0 k min ( D 0 ) = 4 k_{\min}(D_0)=4 k m i n ( D 0 ) = 4 N N N
Example 6.19 (A seven-party star with k min = 8 k_{\min}=8 k m i n = 8
Z 7 : 4 A + 3 B + 4 C + 4 D + 4 E + 3 F + 4 G + 2 A B C D E F G ≥ A B C G + A B D E + A C E F + B C E F + B E F G + C D E G + C D F G (37) Z_7:\qquad4A+3B+4C+4D+4E+3F+4G+2ABCDEFG \ge ABCG+ABDE+ACEF+BCEF+BEFG+CDEG+CDFG \tag*{(37)} Z 7 : 4 A + 3 B + 4 C + 4 D + 4 E + 3 F + 4 G + 2 A B C D E F G ≥ A B C G + A B D E + A C E F + B C E F + B E F G + C D E G + C D F G (37) has no complementary pair of words. With the coordinates in the order of its RHS terms, the point c = 1 8 ( 2 , 1 , 1 , 6 , 3 , 1 , 2 ) c=\frac{1}{8}(2,1,1,6,3,1,2) c = 8 1 ( 2 , 1 , 1 , 6 , 3 , 1 , 2 ) Π ( Z 7 ) = { c } \Pi(Z_7)=\{c\} Π ( Z 7 ) = { c } k Z 7 kZ_7 k Z 7 8 ∣ k 8\mid k 8 ∣ k k min ( Z 7 ) = 8 k_{\min}(Z_7)=8 k m i n ( Z 7 ) = 8 8 Z 7 8Z_7 8 Z 7 k min ( Z 7 ) = 8 k_{\min}(Z_7)=8 k m i n ( Z 7 ) = 8 k Z 7 kZ_7 k Z 7 k = 1 , … , 7 k=1,\ldots,7 k = 1 , … , 7 8 Z 7 8Z_7 8 Z 7
Table 3. Star inequalities with large least scaling. The point is the unique point of the star polytope, in the coin order of the construction for D j D_j D j Z 7 Z_7 Z 7 G 9 G_9 G 9 H 9 , … , H 17 H_9,\ldots,H_{17} H 9 , … , H 17 k min k_{\min} k m i n k k k
Table 3 also lists five star inequalities on 9 to 17 parties, written out in Appendix C.2, whose least scaling exceeds 2 ( N + 1 ) / 4 2^{(N+1)/4} 2 ( N + 1 ) /4 Z 7 Z_7 Z 7 G 9 G_9 G 9 Q T Q_T Q T H 9 H_9 H 9 H 11 H_{11} H 11 H 15 H_{15} H 15 1 , 2 , … , 8 1,2,\ldots,8 1 , 2 , … , 8 H 17 H_{17} H 17 8 × 9 8\times9 8 × 9
Superexponential least scaling of star inequalities
Let B B B n × ( n + 1 ) n\times(n+1) n × ( n + 1 ) n n n n n n B B B R w \mathbb{R}w R w w w w
ν ( B ) = max { ∣ w K w K ′ ∣ : K , K ′ ∈ [ n + 1 ] , w K ′ ≠ 0 } , (38) \nu(B)=\max\left\{\left|\frac{w_K}{w_{K'}}\right|:K,K'\in[n+1],\,w_{K'}\ne0\right\}, \tag*{(38)} ν ( B ) = max { w K ′ w K : K , K ′ ∈ [ n + 1 ] , w K ′ = 0 } , (38) which does not depend on the choice of w w w [26 ] , where it is denoted ζ ( B ) \zeta(B) ζ ( B ) B B B ± 1 \pm1 ± 1 n + 1 n+1 n + 1 − 1 -1 − 1 n n n w w w ν ( B ) \nu(B) ν ( B ) n n n
Corollary 6.22 (Superexponential least scaling of star inequalities). (i) For every n × ( n + 1 ) n \times(n+1) n × ( n + 1 ) B B B ± 1 \pm1 ± 1 n n n Q Q Q 2 n + 1 2n+1 2 n + 1 ν ( B ) ≤ k min ( Q ) < ∞ \nu(B) \le k_{\min}(Q) < \infty ν ( B ) ≤ k m i n ( Q ) < ∞
(ii) For every N ≥ 3 N \ge3 N ≥ 3 Q N Q_N Q N N N N k min ( Q N ) < ∞ k_{\min}(Q_N) < \infty k m i n ( Q N ) < ∞
log 2 k min ( Q N ) ≥ N 4 log 2 N − ( 5 4 + o ( 1 ) ) N ( N → ∞ ) . (39) \log_2 k_{\min}(Q_N) \ge\frac{N}{4}\log_2 N-\left(\frac{5}{4}+o(1)\right)N \qquad(N \to\infty). \tag*{(39)} log 2 k m i n ( Q N ) ≥ 4 N log 2 N − ( 4 5 + o ( 1 ) ) N ( N → ∞ ) . (39) Part (ii) rests on a proposition of Alon and Vũ [26 ] , which gives for every n n n B B B ν ( B ) ≥ 2 1 2 n log 2 n − n ( 2 + o ( 1 ) ) \nu(B) \ge2^{\frac{1}{2}n\log_2 n-n(2+o(1))} ν ( B ) ≥ 2 2 1 n l o g 2 n − n ( 2 + o ( 1 )) [26 ] , which constructs ( − 1 , 1 ) (-1,1) ( − 1 , 1 ) § 7 . After the signs of some columns of B B B B B B k min = q ≥ max K ω K ≥ ν ( B ) k_{\min}=q \ge\max_K \omega_K \ge\nu(B) k m i n = q ≥ max K ω K ≥ ν ( B ) q q q B B B K K K ω K \omega_K ω K q ≥ ν ( B ) q \ge\nu(B) q ≥ ν ( B ) [26 ] . For even N N N ρ O = 1 \rho_O=1 ρ O = 1 ρ O > 0 \rho_O>0 ρ O > 0 z z z Theorem 6.10 , which has only the bit of S ( [ N ] ) \mathcal{S}([N]) S ([ N ]) A ( Q ) \mathcal{A}(Q) A ( Q ) ( ⇒ ) (\Rightarrow) ( ⇒ ) A ( Q ) \mathcal{A}(Q) A ( Q ) k min A ( Q ) = k min ( Q ) k_{\min}^{\mathcal{A}}(Q)=k_{\min}(Q) k m i n A ( Q ) = k m i n ( Q ) k min A k_{\min}^{\mathcal{A}} k m i n A
The least scaling of a star inequality with a nonempty polytope is also bounded from above. Let Δ ( n ) \Delta(n) Δ ( n ) n × n n \times n n × n { 0 , 1 } \{0,1\} { 0 , 1 } Δ ( 0 ) = 1 \Delta(0)=1 Δ ( 0 ) = 1 complement-closed if, for the word η \eta η β − η \beta-\eta β − η Q T Q_T Q T N N N
Proposition 6.24 (An upper bound for star inequalities). Let Q Q Q N N N Π ( Q ) ≠ ∅ \Pi(Q) \ne\varnothing Π ( Q ) = ∅
k min ( Q ) ≤ 2 Δ ( N ) ≤ 2 ( N + 1 ) ( N + 1 ) / 2 2 − N . (40) k_{\min}(Q) \le2\Delta(N) \le2(N+1)^{(N+1)/2}2^{-N}. \tag*{(40)} k m i n ( Q ) ≤ 2Δ ( N ) ≤ 2 ( N + 1 ) ( N + 1 ) /2 2 − N . (40) If Q Q Q k min ( Q ) ≤ 2 Δ ( ⌊ ( N − 1 ) / 2 ⌋ ) k_{\min}(Q) \le2\Delta(\lfloor(N-1)/2 \rfloor) k m i n ( Q ) ≤ 2Δ (⌊( N − 1 ) /2 ⌋)
The proof is in Appendix B.§ 7 . By Theorem 6.10 , k min ( Q ) k_{\min}(Q) k m i n ( Q ) v v v Π ( Q ) \Pi(Q) Π ( Q ) v v v ± 1 \pm1 ± 1 N ≥ 3 N \ge3 N ≥ 3 2 ≤ ∣ J K ∣ ≤ N − 1 2 \le|J_K| \le N-1 2 ≤ ∣ J K ∣ ≤ N − 1 N ≥ 3 N \ge3 N ≥ 3 N N / 2 N^{N/2} N N /2 N N / 2 N^{N/2} N N /2 2 ( 1 + 1 N ) N / 2 ( N + 1 ) 1 / 2 2 − N ≤ 2 e 1 / 2 ( N + 1 ) 1 / 2 2 − N < 1 2(1+\frac{1}{N})^{N/2}(N+1)^{1/2}2^{-N} \le2e^{1/2}(N+1)^{1/2}2^{-N} < 1 2 ( 1 + N 1 ) N /2 ( N + 1 ) 1/2 2 − N ≤ 2 e 1/2 ( N + 1 ) 1/2 2 − N < 1 Corollary 6.22 , the largest finite value of k min k_{\min} k m i n N N N N ( 1 / 4 − o ( 1 ) ) N N^{(1/4-o(1))N} N ( 1/4 − o ( 1 )) N N ( 1 / 2 + o ( 1 ) ) N N^{(1/2+o(1))N} N ( 1/2 + o ( 1 )) N Corollary 6.22 , the second bound of the proposition is N ( 1 / 4 + o ( 1 ) ) N N^{(1/4+o(1))N} N ( 1/4 + o ( 1 )) N 1 4 \frac{1}{4} 4 1 Corollary 6.22 cannot be improved.
Adding parties that lie in no term changes neither validity [6 , 19 ] nor the maps: a graph model for the larger set of parties is one for the smaller set once the boundary vertices of the new parties are labeled O O O k min k_{\min} k m i n N N N N N N Table 3 it is at least 8 for N = 7 , 8 N=7,8 N = 7 , 8 9 ≤ N ≤ 14 9 \le N \le14 9 ≤ N ≤ 14 N ≥ 15 N \ge15 N ≥ 15 N = 7 , 9 N=7,9 N = 7 , 9 Z 7 Z_7 Z 7 G 9 G_9 G 9 H 15 H_{15} H 15 N N N Corollary 6.22 it grows at least as N ( 1 / 4 − o ( 1 ) ) N N^{(1/4-o(1))N} N ( 1/4 − o ( 1 )) N S ( [ N ] ) S([N]) S ([ N ]) Corollary 6.22 treats even N N N
Scope of the star results
By Lemma 6.8 , every star inequality with a nonempty polytope, in particular every one in § 6.2 –§ 6.4 and every one behind the superexponential bound of Corollary 6.22 , is implied by subadditivity. So none of the values of k min k_{\min} k m i n § 6.2 –§ 6.4 says anything about how much scaling the facets of H E C N \mathrm{HEC}_N HEC N (6) gives Q ⋅ r i O = ρ i + ρ O − ∣ η ( i ) ∣ Q\cdot r_{iO}=\rho_i+\rho_O-\lvert\eta^{(i)}\rvert Q ⋅ r i O = ρ i + ρ O − ∣ η ( i ) ∣ Q T Q_T Q T ∣ T i ∣ + 1 − ∣ T i ∣ = 1 \lvert T_i\rvert+1-\lvert T_i\rvert=1 ∣ T i ∣ + 1 − ∣ T i ∣ = 1 i ≤ N − 1 i\leq N-1 i ≤ N − 1 Q T Q_T Q T D j D_j D j Corollary 6.22 are, and neither are Z 7 Z_7 Z 7 Q ′ Q' Q ′ Q Q Q ∣ η ( i ) ∣ = ρ i + ρ O \lvert\eta^{(i)}\rvert=\rho_i+\rho_O ∣ η ( i ) ∣ = ρ i + ρ O i i i c ∈ Π ( Q ) c\in\Pi(Q) c ∈ Π ( Q ) ∣ η ( i ) ∣ ≤ ∥ c ∥ 1 + ∥ η ( i ) − c ∥ 1 ≤ ρ O + ρ i \lvert\eta^{(i)}\rvert\leq\lVert c\rVert_1+\lVert\eta^{(i)}-c\rVert_1\leq\rho_O+\rho_i ∣ η ( i ) ∣ ≤ ∥ c ∥ 1 + ∥ η ( i ) − c ∥ 1 ≤ ρ O + ρ i c K = 0 c_K=0 c K = 0 i ∉ J K i\notin J_K i ∈ / J K J K J_K J K Π ( Q ) ⊆ { 0 } \Pi(Q)\subseteq\{0\} Π ( Q ) ⊆ { 0 } Theorem 6.10 gives k min ( Q ) ∈ { 1 , ∞ } k_{\min}(Q)\in\{1,\infty\} k m i n ( Q ) ∈ { 1 , ∞ } 1 < k min < ∞ 1<k_{\min}<\infty 1 < k m i n < ∞ § 3 and § 4 are not star inequalities, and the star results do not cover them. Their least scalings, where we know them, are determined in § 3 and § 6.1 . More generally, none of our inequalities without an unscaled map is known to define a facet, so our results do not bear on the empirical remark of Grimaldi, Headrick, Hubeny and Shteyner that rescaling does not create maps for the fully split presentation, made in their discussion of primitive, that is facet-defining, inequalities [16 ] . The one facet we treat, F 7 F_7 F 7 k min A ( F 7 ) = 1 k_{\min}^{A}(F_7)=1 k m i n A ( F 7 ) = 1
Conclusions
The question was whether valid holographic entropy inequalities that are balanced or superbalanced have contraction proofs without rescaling. In § 3 and § 4 it was shown that neither balance nor superbalance guarantees an unscaled map: a balanced seven-party inequality and a superbalanced six-party inequality fail at a single point of the cube, and for superbalanced eight- and seven-party inequalities the failure survives five splittings by instances of MMI. In § 5 one failure was followed to a facet F 7 F_7 F 7 H E C 7 \mathrm{HEC}_7 HEC 7 § 6 the least scaling of star inequalities was described by the lattice points of a polytope, and coin weighings gave star inequalities whose least scaling grows faster than exponentially with N N N
Multiple lines of generalization lie open. First, the least scaling of the superbalanced failures. For E 0 E_0 E 0 E 1 E_1 E 1 E 3 E_3 E 3 E 4 E_4 E 4 2 2 2 Definition 2.10 , k Q kQ k Q k k k U 6 U_6 U 6 E 2 E_2 E 2 E 5 E_5 E 5 Q 8 Q_8 Q 8 Q 8 ′ Q'_8 Q 8 ′ Q 8 ′ ′ Q''_8 Q 8 ′′ § 4.3 , we do not know k min k_{\min} k m i n k Q kQ k Q k k k § 4 would rule out. Second, whether some facet of H E C N \mathrm{HEC}_N HEC N V 7 V_7 V 7 V 7 ′ V'_7 V 7 ′ P 7 P_7 P 7 E 0 E_0 E 0 § 5 . We do not know whether they are facets, and the half-sum 1 2 ( V 7 ′ + P 7 ) \frac{1}{2}(V'_7+P_7) 2 1 ( V 7 ′ + P 7 ) V 7 ′ V'_7 V 7 ′ P 7 P_7 P 7 F 7 F_7 F 7 { 0 , 1 } 20 \{0,1\}^{20} { 0 , 1 } 20 N ≤ 5 N\leq5 N ≤ 5 N ( 1 / 4 − o ( 1 ) ) N N^{(1/4-o(1))N} N ( 1/4 − o ( 1 )) N Theorem 1.1 (d) and the upper bound N ( 1 / 2 + o ( 1 ) ) N N^{(1/2+o(1))N} N ( 1/2 + o ( 1 )) N 1 4 \frac{1}{4} 4 1 § 6.4 , and for valid inequalities that are not star inequalities we give no upper bound. In work to be reported separately we construct valid balanced inequalities whose finite least scaling grows faster than any power of N N N N N N
The certificates
Every statement of this paper that rests on a computation is of one of four kinds: that an inequality has no integer map on a given domain (possibly with a symmetry imposed), that it has an explicit rational or integer map, that a set of explicit graph models has a given rank, or that a graph model violates a given inequality. For each kind we say what is computed, why it proves the statement that the text needs, and in which arithmetic. The certificates and the programs that check them are in the code repository, and Table 4 and Table 5 list, for each statement, the domain, the certificate and the number of independent implementations that produced or checked it.
Table 5. The certificates of Section 6, in the format of Table 4. The domain 0 , z , x ( i ) 0,z,x^{(i)} 0 , z , x ( i ) N + 2 N+2 N + 2
Non-existence of maps: SAT encodings and DRAT proofs
Fix an inequality Q Q Q k ≥ 1 k \ge1 k ≥ 1 Ω \Omega Ω { 0 , 1 } L \{0,1\}^{L} { 0 , 1 } L A ( Q ) A(Q) A ( Q ) U ( Q ) U(Q) U ( Q ) (9) . Whether k Q kQ k Q Ω \Omega Ω [13 ] , which we write as a Boolean formula in conjunctive normal form (CNF). Earlier searches for contraction maps used a greedy extension algorithm [6 ] and deterministic rules [13 ] , and integer programs were used to test invalidity [19 ] . By Lemma 2.12 , the contraction condition needs to be imposed only on pairs irreducible in Ω \Omega Ω d α ( u , v ) ≥ ∣ β ∣ d_{\alpha}(u,v) \ge|\beta| d α ( u , v ) ≥ ∣ β ∣ ∑ r ∣ n r ( u ) − n r ( v ) ∣ ≤ k ∣ β ∣ \sum_r |n_r(u)-n_r(v)| \le k|\beta| ∑ r ∣ n r ( u ) − n r ( v ) ∣ ≤ k ∣ β ∣ Table 4 were implemented separately.
Both encodings have, for each pair u , v u,v u , v u u u v v v [32 ] , sequential counters [33 ] or cardinality networks [34 ] depending on the implementation, partly through PySAT [35 ] , that allows at most k d α ( u , v ) kd_{\alpha}(u,v) k d α ( u , v ) split encoding uses Lemma 2.9 , with one variable for each point u ∈ Ω u \in\Omega u ∈ Ω k ∣ β ∣ k|\beta| k ∣ β ∣ order encoding represents each count n r ( u ) ∈ { 0 , … , k β r } n_r(u) \in\{0,\ldots,k\beta_r\} n r ( u ) ∈ { 0 , … , k β r } [ n r ( u ) ≥ s ] [n_r(u) \ge s] [ n r ( u ) ≥ s ] 1 ≤ s ≤ k β r 1 \le s \le k\beta_r 1 ≤ s ≤ k β r [ n r ( u ) ≥ s + 1 ] ⇒ [ n r ( u ) ≥ s ] [n_r(u) \ge s+1] \Rightarrow[n_r(u) \ge s] [ n r ( u ) ≥ s + 1 ] ⇒ [ n r ( u ) ≥ s ] s s s u u u v v v ∣ n r ( u ) − n r ( v ) ∣ |n_r(u)-n_r(v)| ∣ n r ( u ) − n r ( v ) ∣
We decided the formulas with the SAT solvers CaDiCaL [36 ] and Kissat [37 ] . For an unsatisfiable formula the solver writes a proof in the DRAT format, a sequence of clauses each of which can be checked by unit propagation or by the resolution-asymmetric-tautology criterion, ending with the empty clause. Every unsatisfiability claim in this paper comes with such a proof, accepted by the checker drat-trim [27 ] , which does not share code with the solvers. For the star inequalities G 9 G_9 G 9 H 9 H_9 H 9 H 11 H_{11} H 11 H 15 H_{15} H 15 H 17 H_{17} H 17 Table 3 the domain is the set of the N + 2 N+2 N + 2 0 0 0 z z z x ( 1 ) , … , x ( N ) x^{(1)},\ldots,x^{(N)} x ( 1 ) , … , x ( N ) z z z Theorem 6.10 with only the bit of S ( [ N ] ) S([N]) S ([ N ]) Theorem 6.10 . A DRAT proof does not certify that the CNF encodes the map problem. That step rests on the encoder. Every non-existence statement was obtained from at least two independent encoders, except those for E 5 E_5 E 5 3 Q 8 3Q_8 3 Q 8 V 7 V_7 V 7 Table 4 ).
Validity: exact maps
A validity certificate for Q Q Q n r ( u ) n_r(u) n r ( u ) u u u A ( Q ) A(Q) A ( Q ) Lemma 2.13 (on the full cube also by the theorem of Bao et al. applied to M Q MQ M Q M M M Q Q Q Definition 2.11 (or takes the full cube) and verifies that the set of points of the certificate is exactly this domain, verifies the pins (7) and the ranges 0 ≤ n r ( u ) ≤ β r 0 \le n_r(u) \le\beta_r 0 ≤ n r ( u ) ≤ β r (8) on every pair of points of A ( Q ) A(Q) A ( Q )
The integer maps for 2 E 0 2E_0 2 E 0 2 E 1 2E_1 2 E 1 2 E 3 2E_3 2 E 3 2 E 4 2E_4 2 E 4 n r ( u ) n_r(u) n r ( u ) u u u r r r
Facets and invalidity: graph models
A graph-model certificate is a finite graph with integer edge weights and labeled boundary vertices. The checker recomputes its entropy vector S G S_G S G [38 ] and NetworkX), one minimum cut per nonempty I ⊆ [ N ] I \subseteq[N] I ⊆ [ N ] Q ⋅ S G = 0 Q \cdot S_G = 0 Q ⋅ S G = 0 X ⋅ S G > 0 X \cdot S_G > 0 X ⋅ S G > 0 Q − ε X Q - \varepsilon X Q − εX ε > 0 \varepsilon> 0 ε > 0 § 4 .
For a facet, the certificate is a list of 2 N − 2 2^N - 2 2 N − 2 Q ⋅ S G = 0 Q \cdot S_G = 0 Q ⋅ S G = 0 p p p p p p 2 N − 2 2^N - 2 2 N − 2 p p p 2 N − 2 2^N - 2 2 N − 2 Q \mathbb{Q} Q Q ⊥ Q^\perp Q ⊥ Q Q Q H E C N \mathrm{HEC}_N HEC N Q Q Q F 7 F_7 F 7
Equivariant maps
A relabeling g ∈ Stab ( Q ) g \in\operatorname{Stab}(Q) g ∈ Stab ( Q ) A ( Q ) \mathcal{A}(Q) A ( Q ) n n n n g ( r ) ( g ⋅ u ) = n r ( u ) n_{g(r)}(g \cdot u) = n_r(u) n g ( r ) ( g ⋅ u ) = n r ( u ) g g g r r r u u u ( u , r ) (u,r) ( u , r ) ( g ⋅ u , g ( r ) ) (g \cdot u,g(r)) ( g ⋅ u , g ( r )) F 7 F_7 F 7 V 7 V_7 V 7
Appendix B. Omitted proofs
This appendix proves the lemmas of Section 2 and the results on star inequalities of Section 6.
Proofs of Lemmas 2.9 and 2.12
Proof of Lemma 2.9. Given f f f n r ( u ) = ∑ s = 1 β r f ( u ) r , s n_r(u) = \sum_{s=1}^{\beta_r} f(u)_{r,s} n r ( u ) = ∑ s = 1 β r f ( u ) r , s f ( x ( i ) ) r , s = [ i ∈ J r ] f(x^{(i)})_{r,s} = [i \in J_r] f ( x ( i ) ) r , s = [ i ∈ J r ] s s s ∑ r ∣ n r ( u ) − n r ( v ) ∣ ≤ ∑ r , s ∣ f ( u ) r , s − f ( v ) r , s ∣ ≤ d α ( u , v ) \sum_r |n_r(u) - n_r(v)| \le\sum_{r,s} |f(u)_{r,s} - f(v)_{r,s}| \le d_\alpha(u,v) ∑ r ∣ n r ( u ) − n r ( v ) ∣ ≤ ∑ r , s ∣ f ( u ) r , s − f ( v ) r , s ∣ ≤ d α ( u , v ) n n n f ( u ) r , s = [ s ≤ n r ( u ) ] f(u)_{r,s} = [s \le n_r(u)] f ( u ) r , s = [ s ≤ n r ( u )] J r J_r J r u u u v v v s s s min ( n r ( u ) , n r ( v ) ) + 1 \min(n_r(u),n_r(v)) + 1 min ( n r ( u ) , n r ( v )) + 1 max ( n r ( u ) , n r ( v ) ) \max(n_r(u),n_r(v)) max ( n r ( u ) , n r ( v )) d 1 ( f ( u ) , f ( v ) ) = ∑ r ∣ n r ( u ) − n r ( v ) ∣ ≤ d α ( u , v ) d_1(f(u),f(v)) = \sum_r |n_r(u) - n_r(v)| \le d_\alpha(u,v) d 1 ( f ( u ) , f ( v )) = ∑ r ∣ n r ( u ) − n r ( v ) ∣ ≤ d α ( u , v ) n n n f ( x ( i ) ) = y ˉ ( i ) f(x^{(i)}) = \bar{y}^{(i)} f ( x ( i ) ) = y ˉ ( i ) f ( 0 ) = 0 f(0) = 0 f ( 0 ) = 0
Proof of Lemma 2.12. By induction on d α ( u , v ) d_\alpha(u,v) d α ( u , v ) u , v u,v u , v z z z d α ( u , v ) = d α ( u , z ) + d α ( z , v ) d_\alpha(u,v) = d_\alpha(u,z) + d_\alpha(z,v) d α ( u , v ) = d α ( u , z ) + d α ( z , v ) d α ( u , v ) d_\alpha(u,v) d α ( u , v ) z ≠ u , v z \ne u,v z = u , v α l > 0 \alpha_l > 0 α l > 0 ∑ r ∣ n r ( u ) − n r ( v ) ∣ ≤ d α ( u , z ) + d α ( z , v ) = d α ( u , v ) \sum_r |n_r(u) - n_r(v)| \le d_\alpha(u,z) + d_\alpha(z,v) = d_\alpha(u,v) ∑ r ∣ n r ( u ) − n r ( v ) ∣ ≤ d α ( u , z ) + d α ( z , v ) = d α ( u , v )
Proof of Lemma 2.13
The words of the graph-model proof lie in A ( Q ) \mathcal{A}(Q) A ( Q ) [19 ] . We include the short proof for completeness.
Lemma B.1 (Minimal min cuts). Fix a graph model and nonempty I , I ′ ⊆ [ N ] I,I' \subseteq[N] I , I ′ ⊆ [ N ] I I I W I W_I W I I I I I ⊆ I ′ I \subseteq I' I ⊆ I ′ W I ⊆ W I ′ W_I \subseteq W_{I'} W I ⊆ W I ′ I ∩ I ′ = ∅ I \cap I' = \varnothing I ∩ I ′ = ∅ W I ∩ W I ′ = ∅ W_I \cap W_{I'} = \varnothing W I ∩ W I ′ = ∅
Proof. The cut weight is submodular, C ( X ∩ Y ) + C ( X ∪ Y ) ≤ C ( X ) + C ( Y ) C(X \cap Y) + C(X \cup Y) \le C(X) + C(Y) C ( X ∩ Y ) + C ( X ∪ Y ) ≤ C ( X ) + C ( Y ) X , Y ⊆ V X,Y \subseteq V X , Y ⊆ V X ∩ Y X \cap Y X ∩ Y X ∪ Y X \cup Y X ∪ Y X ∩ Y X \cap Y X ∩ Y X ∪ Y X \cup Y X ∪ Y X X X Y Y Y X ∩ Y X \cap Y X ∩ Y X ∪ Y X \cup Y X ∪ Y X X X Y Y Y
(a) If W , W ′ W,W' W , W ′ I I I W ∩ W ′ W\cap W' W ∩ W ′ W ∪ W ′ W\cup W' W ∪ W ′ I I I 2 S ( I ) ≤ C ( W ∩ W ′ ) + C ( W ∪ W ′ ) ≤ C ( W ) + C ( W ′ ) = 2 S ( I ) 2S(I)\leq C(W\cap W')+C(W\cup W')\leq C(W)+C(W')=2S(I) 2 S ( I ) ≤ C ( W ∩ W ′ ) + C ( W ∪ W ′ ) ≤ C ( W ) + C ( W ′ ) = 2 S ( I ) W ∩ W ′ W\cap W' W ∩ W ′
(b) The set W I ∩ W I ′ W_I\cap W_{I'} W I ∩ W I ′ I I I W I ∪ W I ′ W_I\cup W_{I'} W I ∪ W I ′ I ′ I' I ′ b − 1 ( I ) ∩ b − 1 ( I ′ ) = b − 1 ( I ) b^{-1}(I)\cap b^{-1}(I')=b^{-1}(I) b − 1 ( I ) ∩ b − 1 ( I ′ ) = b − 1 ( I ) b − 1 ( I ) ∪ b − 1 ( I ′ ) = b − 1 ( I ′ ) b^{-1}(I)\cup b^{-1}(I')=b^{-1}(I') b − 1 ( I ) ∪ b − 1 ( I ′ ) = b − 1 ( I ′ ) [39 ] gives C ( W I ∩ W I ′ ) + C ( W I ∪ W I ′ ) ≤ S ( I ) + S ( I ′ ) C(W_I\cap W_{I'})+C(W_I\cup W_{I'})\leq S(I)+S(I') C ( W I ∩ W I ′ ) + C ( W I ∪ W I ′ ) ≤ S ( I ) + S ( I ′ ) W I ∩ W I ′ W_I\cap W_{I'} W I ∩ W I ′ I I I W I W_I W I W I ⊆ W I ′ W_I\subseteq W_{I'} W I ⊆ W I ′
(c) Let X = W I ∩ W I ′ X=W_I\cap W_{I'} X = W I ∩ W I ′ b − 1 ( I ) ∩ b − 1 ( I ′ ) = ∅ b^{-1}(I)\cap b^{-1}(I')=\varnothing b − 1 ( I ) ∩ b − 1 ( I ′ ) = ∅ X ≠ ∅ X\neq\varnothing X = ∅ a 1 a_1 a 1 a 2 a_2 a 2 a 3 a_3 a 3 X X X W I ∖ W I ′ W_I\setminus W_{I'} W I ∖ W I ′ W I ′ ∖ W I W_{I'}\setminus W_I W I ′ ∖ W I V ∖ ( W I ∪ W I ′ ) V\setminus(W_I\cup W_{I'}) V ∖ ( W I ∪ W I ′ ) W I ∖ X W_I\setminus X W I ∖ X I I I X X X W I W_I W I X X X W I W_I W I X X X W I ∖ W I ′ W_I\setminus W_{I'} W I ∖ W I ′ C ( W I ∖ X ) = S ( I ) + a 1 − a 2 − a 3 C(W_I\setminus X)=S(I)+a_1-a_2-a_3 C ( W I ∖ X ) = S ( I ) + a 1 − a 2 − a 3 W I W_I W I I I I a 1 − a 2 − a 3 > 0 a_1-a_2-a_3>0 a 1 − a 2 − a 3 > 0 a 2 − a 1 − a 3 > 0 a_2-a_1-a_3>0 a 2 − a 1 − a 3 > 0 a 3 < 0 a_3<0 a 3 < 0 □ \square □
Proof of Lemma 2.13. It suffices to prove Q ⋅ S ≥ 0 Q\cdot S\geq0 Q ⋅ S ≥ 0 W l = W I l W_l=W_{I_l} W l = W I l l l l v v v x ( v ) ∈ { 0 , 1 } L x(v)\in\{0,1\}^{L} x ( v ) ∈ { 0 , 1 } L x ( v ) l = [ v ∈ W l ] x(v)_l=[v\in W_l] x ( v ) l = [ v ∈ W l ]
Step 1: the words lie in A ( Q ) \mathcal{A}(Q) A ( Q ) If x ( v ) l = x ( v ) l ′ = 1 x(v)_l=x(v)_{l'}=1 x ( v ) l = x ( v ) l ′ = 1 W l ∩ W l ′ ≠ ∅ W_l\cap W_{l'}\neq\varnothing W l ∩ W l ′ = ∅ I l ∩ I l ′ ≠ ∅ I_l\cap I_{l'}\neq\varnothing I l ∩ I l ′ = ∅ x ( v ) l = 1 x(v)_l=1 x ( v ) l = 1 I l ⊆ I l ′ I_l\subseteq I_{l'} I l ⊆ I l ′ v ∈ W l ⊆ W l ′ v\in W_l\subseteq W_{l'} v ∈ W l ⊆ W l ′ x ( v ) l ′ = 1 x(v)_{l'}=1 x ( v ) l ′ = 1 i i i I l I_l I l i ∈ I l i\in I_l i ∈ I l x ( i ) x^{(i)} x ( i ) O O O I l I_l I l 0 0 0 n r ( v ) = n r ( x ( v ) ) n_r(v)=n_r(x(v)) n r ( v ) = n r ( x ( v )) v v v Step 2: layer cake. Fix r r r t ∈ [ 0 , β r ) t \in[0,\beta_r) t ∈ [ 0 , β r ) U r ( t ) = { v ∈ V : n r ( v ) > t } U_r(t)=\{v\in V:n_r(v)>t\} U r ( t ) = { v ∈ V : n r ( v ) > t } i i i n r ( v ) = β r [ i ∈ J r ] n_r(v)=\beta_r[i\in J_r] n r ( v ) = β r [ i ∈ J r ] t t t i ∈ J r i\in J_r i ∈ J r O O O n r ( v ) = 0 ≤ t n_r(v)=0\le t n r ( v ) = 0 ≤ t U r ( t ) U_r(t) U r ( t ) J r J_r J r C ( U r ( t ) ) ≥ S ( J r ) C(U_r(t))\ge S(J_r) C ( U r ( t )) ≥ S ( J r ) e e e u e , v e u_e,v_e u e , v e U r ( t ) U_r(t) U r ( t ) t t t [ min ( n r ( u e ) , n r ( v e ) ) , max ( n r ( u e ) , n r ( v e ) ) ) [\min(n_r(u_e),n_r(v_e)),\max(n_r(u_e),n_r(v_e))) [ min ( n r ( u e ) , n r ( v e )) , max ( n r ( u e ) , n r ( v e ))) [ 0 , β r ] [0,\beta_r] [ 0 , β r ] ∣ n r ( u e ) − n r ( v e ) ∣ |n_r(u_e)-n_r(v_e)| ∣ n r ( u e ) − n r ( v e ) ∣ t ↦ C ( U r ( t ) ) t\mapsto C(U_r(t)) t ↦ C ( U r ( t )) [ 0 , β r ) [0,\beta_r) [ 0 , β r )
β r S ( J r ) ≤ ∫ 0 β r C ( U r ( t ) ) d t = ∑ e ∈ E w e ∣ n r ( u e ) − n r ( v e ) ∣ . (41) \beta_r S(J_r)\le\int_0^{\beta_r}C(U_r(t))\,dt=\sum_{e\in E}w_e|n_r(u_e)-n_r(v_e)|. \tag*{(41)} β r S ( J r ) ≤ ∫ 0 β r C ( U r ( t )) d t = e ∈ E ∑ w e ∣ n r ( u e ) − n r ( v e ) ∣. (41) Step 3: summing. By Step 1 the words of both endpoints of every edge lie in A ( Q ) \mathcal{A}(Q) A ( Q ) r r r
∑ r = 1 R β r S ( J r ) ≤ ∑ e ∈ E w e ∑ r = 1 R ∣ n r ( u e ) − n r ( v e ) ∣ ≤ ∑ e ∈ E w e d α ( x ( u e ) , x ( v e ) ) = ∑ l = 1 L α l ∑ e ∈ E w e ∣ x ( u e ) l − x ( v e ) l ∣ . \begin{aligned}
\sum_{r=1}^{R}\beta_rS(J_r)\le\sum_{e\in E}w_e\sum_{r=1}^{R}|n_r(u_e)-n_r(v_e)|\le\sum_{e\in E}w_ed_{\alpha}(x(u_e),x(v_e)) \\
&=\sum_{l=1}^{L}\alpha_l\sum_{e\in E}w_e|x(u_e)_l-x(v_e)_l|.
\end{aligned} r = 1 ∑ R β r S ( J r ) ≤ e ∈ E ∑ w e r = 1 ∑ R ∣ n r ( u e ) − n r ( v e ) ∣ ≤ e ∈ E ∑ w e d α ( x ( u e ) , x ( v e )) = l = 1 ∑ L α l e ∈ E ∑ w e ∣ x ( u e ) l − x ( v e ) l ∣. The inner sum on the right is the weight of the edges cut by W l W_l W l S ( I l ) S(I_l) S ( I l ) ∑ r β r S ( J r ) ≤ ∑ l α l S ( I l ) \sum_r\beta_rS(J_r)\le\sum_l\alpha_lS(I_l) ∑ r β r S ( J r ) ≤ ∑ l α l S ( I l )
Star inequalities
This part of the appendix proves Theorems 6.10, 6.14 and 6.17, Corollary 6.22, Proposition 6.24 and Lemmas 6.5 and 6.8. Notation is that of § 6 : Q Q Q (26) with RHS terms J 1 , … , J m J_1,\ldots,J_m J 1 , … , J m β K \beta_K β K ρ i \rho_i ρ i η ( i ) \eta^{(i)} η ( i ) Π ( Q ) \Pi(Q) Π ( Q )
Proof of Theorem 6.10
The cube. The LHS terms of Q Q Q { i } \{i\} { i } ρ i > 0 \rho_i>0 ρ i > 0 [ N ] [N] [ N ] ρ O > 0 \rho_O>0 ρ O > 0 ⋆ \star ⋆ [ N ] [N] [ N ] 0 0 0 B = { 0 , 1 } [ N ] ∪ { ⋆ } \mathcal{B}=\{0,1\}^{[N]\cup\{\star\}} B = { 0 , 1 } [ N ] ∪ { ⋆ } i i i ρ i \rho_i ρ i ⋆ \star ⋆ ρ O \rho_O ρ O d ( x , x ′ ) = ∑ i ∈ [ N ] ρ i ∣ x i − x i ′ ∣ + ρ O ∣ x ⋆ − x ⋆ ′ ∣ d(x,x')=\sum_{i\in[N]}\rho_i|x_i-x'_i|+\rho_O|x_\star-x'_\star| d ( x , x ′ ) = ∑ i ∈ [ N ] ρ i ∣ x i − x i ′ ∣ + ρ O ∣ x ⋆ − x ⋆ ′ ∣ i i i { i } \{i\} { i } [ N ] [N] [ N ] e i + e ⋆ e_i+e_\star e i + e ⋆ 0 0 0 k ≥ 1 k\ge1 k ≥ 1 k Q kQ k Q n : B → ∏ K = 1 m { 0 , 1 , … , k β K } n:\mathcal{B}\to\prod_{K=1}^{m}\{0,1,\ldots,k\beta_K\} n : B → ∏ K = 1 m { 0 , 1 , … , k β K }
n ( e i + e ⋆ ) = k η ( i ) ( i ∈ [ N ] ) , n ( 0 ) = 0 , ∥ n ( x ) − n ( x ′ ) ∥ 1 ≤ k d ( x , x ′ ) ( x , x ′ ∈ B ) . (42) n(e_i+e_\star)=k\eta^{(i)}\quad(i\in[N]),\qquad n(0)=0,\qquad\|n(x)-n(x')\|_1\le kd(x,x')\quad(x,x'\in\mathcal{B}). \tag*{(42)} n ( e i + e ⋆ ) = k η ( i ) ( i ∈ [ N ]) , n ( 0 ) = 0 , ∥ n ( x ) − n ( x ′ ) ∥ 1 ≤ k d ( x , x ′ ) ( x , x ′ ∈ B ) . (42) If all radii are positive, B \mathcal{B} B Q Q Q k Q kQ k Q π \pi π B \mathcal{B} B Q Q Q e i + e ⋆ e_i+e_\star e i + e ⋆ i i i 0 0 0 0 0 0 d ( x , x ′ ) = d α ( π x , π x ′ ) d(x,x')=d_\alpha(\pi x,\pi x') d ( x , x ′ ) = d α ( π x , π x ′ ) n ′ n' n ′ k Q kQ k Q n = n ′ ∘ π n=n'\circ\pi n = n ′ ∘ π n n n l l l 0 0 0 ∥ n ( x ) − n ( x ⊕ e l ) ∥ 1 ≤ 0 \|n(x)-n(x\oplus e_l)\|_1\le0 ∥ n ( x ) − n ( x ⊕ e l ) ∥ 1 ≤ 0 n n n n ′ ∘ π n'\circ\pi n ′ ∘ π n ′ n' n ′ Q Q Q k Q kQ k Q
Edges suffice. If x x x x ′ x' x ′ l 1 , … , l s l_1,\ldots,l_s l 1 , … , l s x = x 0 , x 1 , … , x s = x ′ x=x_0,x_1,\ldots,x_s=x' x = x 0 , x 1 , … , x s = x ′ d ( x , x ′ ) = ∑ t d ( x t − 1 , x t ) d(x,x')=\sum_t d(x_{t-1},x_t) d ( x , x ′ ) = ∑ t d ( x t − 1 , x t ) ∥ ⋅ ∥ 1 \|\cdot\|_1 ∥ ⋅ ∥ 1 x ⊕ e l x\oplus e_l x ⊕ e l
∥ n ( x ) − n ( x ⊕ e l ) ∥ 1 ≤ k ρ l for all x ∈ B and l ∈ [ N ] ∪ { ⋆ } , (43) \|n(x)-n(x\oplus e_l)\|_1\le k\rho_l\qquad\text{for all }x\in\mathcal{B}\text{ and }l\in[N]\cup\{\star\}, \tag*{(43)} ∥ n ( x ) − n ( x ⊕ e l ) ∥ 1 ≤ k ρ l for all x ∈ B and l ∈ [ N ] ∪ { ⋆ } , (43) where ρ ⋆ = ρ O \rho_\star=\rho_O ρ ⋆ = ρ O
( ⇒ ) (\Rightarrow) ( ⇒ ) n n n z = e ⋆ z=e_\star z = e ⋆ z z z e i + e ⋆ e_i+e_\star e i + e ⋆ i i i 0 0 0 ⋆ \star ⋆ d ( z , e i + e ⋆ ) = ρ i d(z,e_i+e_\star)=\rho_i d ( z , e i + e ⋆ ) = ρ i i ∈ [ N ] i\in[N] i ∈ [ N ] d ( z , 0 ) = ρ O d(z,0)=\rho_O d ( z , 0 ) = ρ O N + 1 N+1 N + 1
∥ n ( z ) − k η ( i ) ∥ 1 ≤ k ρ i ( i ∈ [ N ] ) , ∥ n ( z ) ∥ 1 ≤ k ρ O . \|n(z)-k\eta^{(i)}\|_1\le k\rho_i\quad(i\in[N]),\qquad\|n(z)\|_1\le k\rho_O. ∥ n ( z ) − k η ( i ) ∥ 1 ≤ k ρ i ( i ∈ [ N ]) , ∥ n ( z ) ∥ 1 ≤ k ρ O . Dividing by k k k c = n ( z ) / k c=n(z)/k c = n ( z ) / k ∏ K [ 0 , β K ] \prod_K[0,\beta_K] ∏ K [ 0 , β K ] k c = n ( z ) ∈ Z m kc=n(z)\in\mathbb{Z}^m k c = n ( z ) ∈ Z m c ∈ Π ( Q ) ∩ 1 k Z m c\in\Pi(Q)\cap\frac{1}{k}\mathbb{Z}^m c ∈ Π ( Q ) ∩ k 1 Z m
( ⇐ ) (\Leftarrow) ( ⇐ ) c ∈ Π ( Q ) c\in\Pi(Q) c ∈ Π ( Q ) k c ∈ Z m kc\in\mathbb{Z}^m k c ∈ Z m a K = k ( β K − c K ) a_K=k(\beta_K-c_K) a K = k ( β K − c K ) b K = k c K b_K=kc_K b K = k c K a K + b K = k β K a_K+b_K=k\beta_K a K + b K = k β K K K K B → { 0 , 1 } \mathcal{B}\to\{0,1\} B → { 0 , 1 } ϕ K 1 ( x ) = [ x i = 1 for some i ∈ J K ] \phi_K^1(x)=[x_i=1\text{ for some }i\in J_K] ϕ K 1 ( x ) = [ x i = 1 for some i ∈ J K ] ϕ K 2 ( x ) = [ x ⋆ = 1 and x i = 0 for all i ∈ [ N ] ∖ J K ] \phi_K^2(x)=[x_\star=1\text{ and }x_i=0\text{ for all }i\in[N]\setminus J_K] ϕ K 2 ( x ) = [ x ⋆ = 1 and x i = 0 for all i ∈ [ N ] ∖ J K ]
n K ( x ) = a K ϕ K 1 ( x ) + b K ϕ K 2 ( x ) . (44) n_K(x)=a_K\phi_K^1(x)+b_K\phi_K^2(x). \tag*{(44)} n K ( x ) = a K ϕ K 1 ( x ) + b K ϕ K 2 ( x ) . (44) Then n K ( x ) ∈ { 0 , a K , b K , k β K } ⊆ { 0 , … , k β K } n_K(x)\in\{0,a_K,b_K,k\beta_K\}\subseteq\{0,\ldots,k\beta_K\} n K ( x ) ∈ { 0 , a K , b K , k β K } ⊆ { 0 , … , k β K } Pins. At x = e i + e ⋆ x=e_i+e_\star x = e i + e ⋆ i i i ϕ K 1 = [ i ∈ J K ] \phi_K^1=[i\in J_K] ϕ K 1 = [ i ∈ J K ] ϕ K 2 = [ i ∉ [ N ] ∖ J K ] = [ i ∈ J K ] \phi_K^2=[i\notin[N]\setminus J_K]=[i\in J_K] ϕ K 2 = [ i ∈ / [ N ] ∖ J K ] = [ i ∈ J K ] n K ( e i + e ⋆ ) = k β K [ i ∈ J K ] = k η K ( i ) n_K(e_i+e_\star)=k\beta_K[i\in J_K]=k\eta_K^{(i)} n K ( e i + e ⋆ ) = k β K [ i ∈ J K ] = k η K ( i ) x = 0 x=0 x = 0 n ( 0 ) = 0 n(0)=0 n ( 0 ) = 0 Edges. The function ϕ K 1 \phi_K^1 ϕ K 1 i ∈ J K i\in J_K i ∈ J K ϕ K 2 \phi_K^2 ϕ K 2 i ∈ [ N ] ∖ J K i\in[N]\setminus J_K i ∈ [ N ] ∖ J K ⋆ \star ⋆ i ∈ [ N ] i\in[N] i ∈ [ N ] n K n_K n K a K a_K a K i ∈ J K i\in J_K i ∈ J K b K b_K b K i ∉ J K i\notin J_K i ∈ / J K
∥ n ( x ) − n ( x ⊕ e i ) ∥ 1 ≤ ∑ K : i ∈ J K k ( β K − c K ) + ∑ K : i ∉ J K k c K = k ∑ K ∣ η K ( i ) − c K ∣ = k ∥ c − η ( i ) ∥ 1 ≤ k ρ i . \lVert n(x)-n(x\oplus e_i)\rVert_1
\le\sum_{K:i\in J_K} k(\beta_K-c_K)+\sum_{K:i\notin J_K}kc_K
= k\sum_K\lvert\eta_K^{(i)}-c_K\rvert
= k\lVert c-\eta^{(i)}\rVert_1
\le k\rho_i. ∥ n ( x ) − n ( x ⊕ e i ) ∥ 1 ≤ K : i ∈ J K ∑ k ( β K − c K ) + K : i ∈ / J K ∑ k c K = k K ∑ ∣ η K ( i ) − c K ∣ = k ∥ c − η ( i ) ∥ 1 ≤ k ρ i . Flipping ⋆ \star ⋆ ϕ K 2 \phi_K^2 ϕ K 2 ∥ n ( x ) − n ( x ⊕ e ⋆ ) ∥ 1 ≤ ∑ K k c K = k ∥ c − η ( O ) ∥ 1 ≤ k ρ O \lVert n(x)-n(x\oplus e_\star)\rVert_1\le\sum_Kkc_K=k\lVert c-\eta^{(O)}\rVert_1\le k\rho_O ∥ n ( x ) − n ( x ⊕ e ⋆ ) ∥ 1 ≤ ∑ K k c K = k ∥ c − η ( O ) ∥ 1 ≤ k ρ O n n n k Q kQ k Q
In the language of Lemma 2.9, ϕ K 1 \phi_K^1 ϕ K 1 ϕ K 2 \phi_K^2 ϕ K 2 S A K 1 \mathrm{SA}_K^1 SA K 1 S A K 2 \mathrm{SA}_K^2 SA K 2 J K J_K J K a K a_K a K b K b_K b K k Q kQ k Q
Consequences. If Π ( Q ) ≠ ∅ \Pi(Q)\ne\emptyset Π ( Q ) = ∅ Q Q Q Π ( Q ) \Pi(Q) Π ( Q ) 1 k Z m \frac{1}{k}\mathbb{Z}^m k 1 Z m k k k k min ( Q ) k_{\min}(Q) k m i n ( Q ) Π ( Q ) = ∅ \Pi(Q)=\emptyset Π ( Q ) = ∅ ( ⇒ ) (\Rightarrow) ( ⇒ ) k Q kQ k Q
Proof of Theorem 6.14
We use the notation of Section 6.3. For ξ ∈ R m \xi\in\mathbb{R}^m ξ ∈ R m T ⊆ [ m ] T\subseteq[m] T ⊆ [ m ] ( 1 − 2 ⋅ 1 T ) ⋅ ξ = ξ ( T ‾ ) − ξ ( T ) (1-2\cdot\mathbf{1}_T)\cdot\xi=\xi(\overline{T})-\xi(T) ( 1 − 2 ⋅ 1 T ) ⋅ ξ = ξ ( T ) − ξ ( T ) ξ \xi ξ T T T
( a ) (a) ( a ) Q T Q_T Q T ω \omega ω T i T_i T i ω ( T i ) = ω ( T i ‾ ) = q / 2 > 0 \omega(T_i)=\omega(\overline{T_i})=q/2>0 ω ( T i ) = ω ( T i ) = q /2 > 0 T i ≠ ∅ T_i\ne\emptyset T i = ∅ T i ≠ [ m ] T_i\ne[m] T i = [ m ] ∣ T i ∣ \lvert T_i\rvert ∣ T i ∣ m − 1 ≥ 1 m-1\ge1 m − 1 ≥ 1 J K J_K J K N N N i ≤ N − 1 i\le N-1 i ≤ N − 1 K ∈ T i K\in T_i K ∈ T i K K K
∑ i : K ∉ T i γ i = ∑ i : K ∈ T i γ i . \sum_{i:K\notin T_i}\gamma_i=\sum_{i:K\in T_i}\gamma_i. i : K ∈ / T i ∑ γ i = i : K ∈ T i ∑ γ i . If K K K T i T_i T i K K K T i T_i T i ∣ J K ∣ ≥ 2 \lvert J_K\rvert\ge2 ∣ J K ∣ ≥ 2 K K K T i T_i T i i ≤ N − 1 i\le N-1 i ≤ N − 1 J K J_K J K ∣ J K ∣ ≤ N − 1 \lvert J_K\rvert\le N-1 ∣ J K ∣ ≤ N − 1 J K = J K ′ J_K=J_{K'} J K = J K ′ K ≠ K ′ K\ne K' K = K ′ K K K K ′ K' K ′ T i T_i T i 1 { K } − 1 { K ′ } \mathbf{1}_{\{K\}}-\mathbf{1}_{\{K'\}} 1 { K } − 1 { K ′ } T i T_i T i ω \omega ω ω \omega ω J K J_K J K Q T Q_T Q T N N N
( a ) (a) ( a ) c = ω / q c=\omega/q c = ω / q m ≥ 2 m\ge2 m ≥ 2 ω \omega ω c ∈ ( 0 , 1 ) m c\in(0,1)^m c ∈ ( 0 , 1 ) m ∥ c ∥ 1 = 1 \lVert c\rVert_1=1 ∥ c ∥ 1 = 1 c ( T i ) = c ( T i ‾ ) = 1 2 c(T_i)=c(\overline{T_i})=\frac12 c ( T i ) = c ( T i ) = 2 1 ∥ c − 1 T i ∥ 1 = 1 + ∣ T i ∣ − 1 = ∣ T i ∣ \lVert c-\mathbf{1}_{T_i}\rVert_1=1+\lvert T_i\rvert-1=\lvert T_i\rvert ∥ c − 1 T i ∥ 1 = 1 + ∣ T i ∣ − 1 = ∣ T i ∣ ∥ c − 1 ∥ 1 = 1 + m − 2 = m − 1 \lVert c-\mathbf{1}\rVert_1=1+m-2=m-1 ∥ c − 1 ∥ 1 = 1 + m − 2 = m − 1 ∥ c − 0 ∥ 1 = 1 \lVert c-0\rVert_1=1 ∥ c − 0 ∥ 1 = 1 c ∈ Π ( Q T ) c\in\Pi(Q_T) c ∈ Π ( Q T )
( a ) (a) ( a ) Π ( Q T ) = { c } \Pi(Q_T)=\{c\} Π ( Q T ) = { c } ξ ∈ Π ( Q T ) \xi\in\Pi(Q_T) ξ ∈ Π ( Q T ) N N N m = ∣ B ∣ m=\lvert\mathcal{B}\rvert m = ∣ B ∣ ∥ ξ ∥ 1 = 1 \lVert\xi\rVert_1=1 ∥ ξ ∥ 1 = 1 i ≤ N − 1 i \le N-1 i ≤ N − 1 ∥ ξ ∥ 1 + ∣ T i ∣ − 2 ξ ( T i ) ≤ ∣ T i ∣ \lVert\xi\rVert_1 + |T_i| - 2\xi(T_i) \le|T_i| ∥ ξ ∥ 1 + ∣ T i ∣ − 2 ξ ( T i ) ≤ ∣ T i ∣ ξ ( T i ‾ ) − ξ ( T i ) ≤ 0 \xi(\overline{T_i}) - \xi(T_i) \le0 ξ ( T i ) − ξ ( T i ) ≤ 0 ξ \xi ξ
∑ i = 1 N − 1 γ i ( ξ ( T i ‾ ) − ξ ( T i ) ) = 0 \sum_{i=1}^{N-1} \gamma_i\bigl(\xi(\overline{T_i})-\xi(T_i)\bigr)=0 i = 1 ∑ N − 1 γ i ( ξ ( T i ) − ξ ( T i ) ) = 0 a sum of nonpositive terms with positive coefficients, so every term vanishes and ξ \xi ξ T i T_i T i ξ = t ω \xi=t\omega ξ = t ω t ∈ R t\in\mathbb{R} t ∈ R ∥ ξ ∥ 1 = 1 \lVert\xi\rVert_1=1 ∥ ξ ∥ 1 = 1 ξ ≥ 0 \xi\ge0 ξ ≥ 0 t = 1 / q t=1/q t = 1/ q ξ = c \xi=c ξ = c
( b ) (b) ( b ) c c c c c c q q q q c K = ω K qc_K=\omega_K q c K = ω K β K = 1 \beta_K=1 β K = 1
( c ) (c) ( c ) k Q T kQ_{\mathcal{T}} k Q T k c ∈ Z m kc\in\mathbb{Z}^m k c ∈ Z m q q q k ω K k\omega_K k ω K K K K ω K \omega_K ω K q q q k k k k min ( Q T ) = q k_{\min}(Q_{\mathcal{T}})=q k m i n ( Q T ) = q
Proof of Theorem 6.17
We use the weights (6.15), the halves (6.16) and the parties of D j D_j D j ω ( T ) = ∑ K ∈ T ω K \omega(T)=\sum_{K\in T}\omega_K ω ( T ) = ∑ K ∈ T ω K
Lemma B.6. For every j ≥ 0 j\ge0 j ≥ 0 q j = 2 j + 2 q_j=2^{j+2} q j = 2 j + 2 ω 1 ( j ) = 1 \omega^{(j)}_1=1 ω 1 ( j ) = 1 T j \mathcal{T}_j T j m j − 1 m_j-1 m j − 1 T ∈ T j T\in\mathcal{T}_j T ∈ T j ω ( j ) ( T ) = q j / 2 \omega^{(j)}(T)=q_j/2 ω ( j ) ( T ) = q j /2
Proof. By induction on j j j j = 0 j=0 j = 0 q 0 = 4 q_0=4 q 0 = 4 ω 1 ( 0 ) = 1 \omega^{(0)}_1=1 ω 1 ( 0 ) = 1 T 0 \mathcal{T}_0 T 0 3 = m 0 − 1 3=m_0-1 3 = m 0 − 1 j j j j + 1 j+1 j + 1 q j + 1 = q j + q j / 2 + q j / 2 = 2 q j = 2 j + 3 q_{j+1}=q_j+q_j/2+q_j/2=2q_j=2^{j+3} q j + 1 = q j + q j /2 + q j /2 = 2 q j = 2 j + 3 T j + 1 \mathcal{T}_{j+1} T j + 1 ( m j − 1 ) + 2 = m j + 1 − 1 (m_j-1)+2=m_{j+1}-1 ( m j − 1 ) + 2 = m j + 1 − 1 T ∪ { u j } T\cup\{u_j\} T ∪ { u j } T 1 ( j ) ∪ { v j } T^{(j)}_1\cup\{v_j\} T 1 ( j ) ∪ { v j } q j / 2 + q j / 2 = q j = q j + 1 / 2 q_j/2+q_j/2=q_j=q_{j+1}/2 q j /2 + q j /2 = q j = q j + 1 /2 { u j , v j } \{u_j,v_j\} { u j , v j } q j = q j + 1 / 2 q_j=q_{j+1}/2 q j = q j + 1 /2
The inequality D j D_j D j Q T Q_{\mathcal{T}} Q T T \mathcal{T} T T ∈ T j T\in\mathcal{T}_j T ∈ T j m = m j ≥ 4 m=m_j\ge4 m = m j ≥ 4 N = 2 ( m j − 1 ) + 1 = N j ≥ 7 N=2(m_j-1)+1=N_j\ge7 N = 2 ( m j − 1 ) + 1 = N j ≥ 7 γ i = 1 \gamma_i=1 γ i = 1 ( 1 − 2 ⋅ 1 T ) + ( 1 − 2 ⋅ 1 T ‾ ) = 0 (1-2\cdot\mathbf{1}_T)+(1-2\cdot\mathbf{1}_{\overline{T}})=0 ( 1 − 2 ⋅ 1 T ) + ( 1 − 2 ⋅ 1 T ) = 0 T ‾ \overline{T} T T T T ξ ∈ R m j \xi\in\mathbb{R}^{m_j} ξ ∈ R m j
ξ ( T ) = ξ ( T ‾ ) for every T ∈ T j (45) \xi(T)=\xi(\overline{T}) \qquad\text{for every }T\in\mathcal{T}_j \tag*{(45)} ξ ( T ) = ξ ( T ) for every T ∈ T j (45) form the line R ω ( j ) \mathbb{R}\omega^{(j)} R ω ( j ) ω ( j ) \omega^{(j)} ω ( j ) ω 1 ( j ) = 1 \omega^{(j)}_1=1 ω 1 ( j ) = 1 Λ j ⊆ R m j \Lambda_j\subseteq\mathbb{R}^{m_j} Λ j ⊆ R m j j j j Λ j = R ω ( j ) \Lambda_j=\mathbb{R}\omega^{(j)} Λ j = R ω ( j ) ω ( j ) \omega^{(j)} ω ( j ) Λ j \Lambda_j Λ j ω ( j ) ( T ) = q j / 2 = ω ( j ) ( T ‾ ) \omega^{(j)}(T)=q_j/2=\omega^{(j)}(\overline{T}) ω ( j ) ( T ) = q j /2 = ω ( j ) ( T ) j = 0 j=0 j = 0
ξ 1 + ξ 2 = ξ 3 + ξ 4 , ξ 1 + ξ 3 = ξ 2 + ξ 4 , ξ 1 + ξ 4 = ξ 2 + ξ 3 . \xi_1+\xi_2=\xi_3+\xi_4,\qquad\xi_1+\xi_3=\xi_2+\xi_4,\qquad\xi_1+\xi_4=\xi_2+\xi_3. ξ 1 + ξ 2 = ξ 3 + ξ 4 , ξ 1 + ξ 3 = ξ 2 + ξ 4 , ξ 1 + ξ 4 = ξ 2 + ξ 3 . Adding the first two gives 2 ξ 1 = 2 ξ 4 2\xi_1=2\xi_4 2 ξ 1 = 2 ξ 4 2 ξ 1 = 2 ξ 3 2\xi_1=2\xi_3 2 ξ 1 = 2 ξ 3 2 ξ 1 = 2 ξ 2 2\xi_1=2\xi_2 2 ξ 1 = 2 ξ 2 ξ = ξ 1 ( 1 , 1 , 1 , 1 ) \xi=\xi_1(1,1,1,1) ξ = ξ 1 ( 1 , 1 , 1 , 1 ) Λ j = R ω ( j ) \Lambda_j=\mathbb{R}\omega^{(j)} Λ j = R ω ( j ) ξ = ( ξ ′ , ξ u , ξ v ) ∈ Λ j + 1 \xi=(\xi',\xi_u,\xi_v)\in\Lambda_{j+1} ξ = ( ξ ′ , ξ u , ξ v ) ∈ Λ j + 1 ξ ′ ∈ R m j \xi'\in\mathbb{R}^{m_j} ξ ′ ∈ R m j ξ u , ξ v \xi_u,\xi_v ξ u , ξ v u j , v j u_j,v_j u j , v j T ⊆ [ m j ] T\subseteq[m_j] T ⊆ [ m j ] T ′ = [ m j ] ∖ T T'=[m_j]\setminus T T ′ = [ m j ] ∖ T T 1 = T 1 ( j ) T_1=T^{(j)}_1 T 1 = T 1 ( j ) T ∪ { u j } T\cup\{u_j\} T ∪ { u j } [ m j + 1 ] [m_{j+1}] [ m j + 1 ] T ′ ∪ { v j } T'\cup\{v_j\} T ′ ∪ { v j } T 1 ∪ { v j } T_1\cup\{v_j\} T 1 ∪ { v j } T 1 ′ ∪ { u j } T'_1\cup\{u_j\} T 1 ′ ∪ { u j } T 1 ∪ { u j } T_1\cup\{u_j\} T 1 ∪ { u j } T 1 ∪ { v j } T_1\cup\{v_j\} T 1 ∪ { v j }
ξ ′ ( T 1 ) + ξ u = ξ ′ ( T 1 ′ ) + ξ v , ξ ′ ( T 1 ) + ξ v = ξ ′ ( T 1 ′ ) + ξ u . \xi'(T_1)+\xi_u=\xi'(T'_1)+\xi_v,\qquad\xi'(T_1)+\xi_v=\xi'(T'_1)+\xi_u. ξ ′ ( T 1 ) + ξ u = ξ ′ ( T 1 ′ ) + ξ v , ξ ′ ( T 1 ) + ξ v = ξ ′ ( T 1 ′ ) + ξ u . Subtracting the second from the first gives 2 ξ u = 2 ξ v 2\xi_u=2\xi_v 2 ξ u = 2 ξ v ξ u = ξ v \xi_u=\xi_v ξ u = ξ v T ∪ { u j } T\cup\{u_j\} T ∪ { u j } ξ ′ ( T ) = ξ ′ ( T ′ ) \xi'(T)=\xi'(T') ξ ′ ( T ) = ξ ′ ( T ′ ) T ∈ T j T\in\mathcal{T}_j T ∈ T j ξ ′ ∈ Λ j \xi'\in\Lambda_j ξ ′ ∈ Λ j ξ ′ = t ω ( j ) \xi'=t\omega^{(j)} ξ ′ = t ω ( j ) t ∈ R t\in\mathbb{R} t ∈ R { u j , v j } \{u_j,v_j\} { u j , v j } ξ u + ξ v = ξ ′ ( [ m j ] ) = t q j \xi_u+\xi_v=\xi'([m_j])=tq_j ξ u + ξ v = ξ ′ ([ m j ]) = t q j ξ u = ξ v = t q j / 2 \xi_u=\xi_v=tq_j/2 ξ u = ξ v = t q j /2 ξ = t ( ω ( j ) , q j / 2 , q j / 2 ) = t ω ( j + 1 ) \xi=t(\omega^{(j)},q_j/2,q_j/2)=t\omega^{(j+1)} ξ = t ( ω ( j ) , q j /2 , q j /2 ) = t ω ( j + 1 ) Λ j + 1 = R ω ( j + 1 ) \Lambda_{j+1}=\mathbb{R}\omega^{(j+1)} Λ j + 1 = R ω ( j + 1 ) ω = ω ( j ) \omega=\omega^{(j)} ω = ω ( j ) q = q j = 2 j + 2 q=q_j=2^{j+2} q = q j = 2 j + 2 2 j + 2 = 2 ( N j + 1 ) / 4 2^{j+2}=2(N_j+1)/4 2 j + 2 = 2 ( N j + 1 ) /4 N j + 1 = 4 j + 8 N_j+1=4j+8 N j + 1 = 4 j + 8
Proofs of Corollary 6.22 and Proposition 6.24
Proof of Corollary 6.22. (i) Let w w w B B B K K K B B B w K w_K w K B w = 0 Bw=0 B w = 0 ± 1 \pm1 ± 1 ν ( B ) \nu(B) ν ( B ) w ≥ 0 w \ge0 w ≥ 0 F = { K : w K > 0 } F=\{K:w_K>0\} F = { K : w K > 0 } F = { K } F=\{K\} F = { K } B w = w K ⋅ ( column K ) = 0 Bw=w_K\cdot(\text{column }K)=0 B w = w K ⋅ ( column K ) = 0 ± 1 \pm1 ± 1 ∣ F ∣ ≥ 2 |F|\ge2 ∣ F ∣ ≥ 2 B F B_F B F n × ∣ F ∣ n\times|F| n × ∣ F ∣ B B B F F F y y y B F y = 0 B_Fy=0 B F y = 0 B y = 0 By=0 B y = 0 w w w B F y = 0 B_Fy=0 B F y = 0 R w F \mathbb{R}w_F R w F F F F [ m ] [m] [ m ] m = ∣ F ∣ m=|F| m = ∣ F ∣ ω \omega ω w F w_F w F b b b B F B_F B F T b = { K : b K = − 1 } T_b=\{K:b_K=-1\} T b = { K : b K = − 1 } b = 1 − 2 ⋅ 1 T b b=\mathbf{1}-2\cdot\mathbf{1}_{T_b} b = 1 − 2 ⋅ 1 T b b ⋅ ξ = ξ ( T b ‾ ) − ξ ( T b ) b\cdot\xi=\xi(\overline{T_b})-\xi(T_b) b ⋅ ξ = ξ ( T b ) − ξ ( T b ) n n n T b T_b T b N − 1 = 2 n N-1=2n N − 1 = 2 n T b T_b T b T b ‾ \overline{T_b} T b b ⋅ ξ = 0 b\cdot\xi=0 b ⋅ ξ = 0 γ i = 1 \gamma_i=1 γ i = 1 2 n + 1 2n+1 2 n + 1 k min = q = ∑ K ω K k_{\min}=q=\sum_K\omega_K k m i n = q = ∑ K ω K ν ( B ) = max K ω K / min K ω K \nu(B)=\max_K\omega_K/\min_K\omega_K ν ( B ) = max K ω K / min K ω K min K ω K ≥ 1 \min_K\omega_K\ge1 min K ω K ≥ 1 k min ≥ max K ω K ≥ ν ( B ) k_{\min}\ge\max_K\omega_K\ge\nu(B) k m i n ≥ max K ω K ≥ ν ( B )
(ii) Let N = 2 n + 1 N=2n+1 N = 2 n + 1 n ≥ 1 n\ge1 n ≥ 1 [26 ] there is an n × ( n + 1 ) n\times(n+1) n × ( n + 1 ) B B B ± 1 \pm1 ± 1 n n n log 2 ν ( B ) ≥ 1 2 n log 2 n − n ( 2 + o ( 1 ) ) \log_2\nu(B)\ge\frac{1}{2}n\log_2 n-n(2+o(1)) log 2 ν ( B ) ≥ 2 1 n log 2 n − n ( 2 + o ( 1 )) Q N Q_N Q N log 2 k min ( Q N ) ≥ log 2 ν ( B ) \log_2 k_{\min}(Q_N)\ge\log_2\nu(B) log 2 k m i n ( Q N ) ≥ log 2 ν ( B ) n = ( N − 1 ) / 2 n=(N-1)/2 n = ( N − 1 ) /2 1 2 n log 2 n = N 4 log 2 N − N 4 + O ( log N ) \frac{1}{2}n\log_2 n=\frac{N}{4}\log_2N-\frac{N}{4}+O(\log N) 2 1 n log 2 n = 4 N log 2 N − 4 N + O ( log N ) n ( 2 + o ( 1 ) ) = ( 1 + o ( 1 ) ) N n(2+o(1))=(1+o(1))N n ( 2 + o ( 1 )) = ( 1 + o ( 1 )) N N = 2 n + 2 N=2n+2 N = 2 n + 2 2 n + 1 2n+1 2 n + 1 T 1 T_1 T 1 γ = 1 2 \gamma=\frac{1}{2} γ = 2 1 T 1 T_1 T 1 γ = 1 \gamma=1 γ = 1 Q N Q_N Q N N N N q q q n = ( N − 2 ) / 2 n=(N-2)/2 n = ( N − 2 ) /2
Proof of Proposition 6.24. By Lemma 6.5, for each i ∈ [ N ] ∪ { O } i\in[N]\cup\{O\} i ∈ [ N ] ∪ { O } ∥ c − η ( i ) ∥ 1 ≤ ρ i \lVert c-\eta^{(i)}\rVert_1\le\rho_i ∥ c − η ( i ) ∥ 1 ≤ ρ i s ( i ) ⋅ c ≤ b i s^{(i)}\cdot c\le b_i s ( i ) ⋅ c ≤ b i s K ( i ) = 1 s^{(i)}_K=1 s K ( i ) = 1 η K ( i ) = 0 \eta^{(i)}_K=0 η K ( i ) = 0 s K ( i ) = − 1 s^{(i)}_K=-1 s K ( i ) = − 1 η K ( i ) = β K \eta^{(i)}_K=\beta_K η K ( i ) = β K b i = ρ i − ∑ K : η K ( i ) = β K β K ∈ Z b_i=\rho_i-\sum_{K:\eta^{(i)}_K=\beta_K}\beta_K\in\mathbb{Z} b i = ρ i − ∑ K : η K ( i ) = β K β K ∈ Z Π ( Q ) \Pi(Q) Π ( Q ) v v v k min ( Q ) k_{\min}(Q) k m i n ( Q ) v v v F = { K : 0 < v K < β K } F=\{K:0<v_K<\beta_K\} F = { K : 0 < v K < β K } t = ∣ F ∣ t=|F| t = ∣ F ∣ v v v F F F 0 0 0 β K \beta_K β K v v v v v v m m m F F F s ( i ) ⋅ v = b i s^{(i)}\cdot v=b_i s ( i ) ⋅ v = b i F F F t t t t t t v F v_F v F M v F = b ′ Mv_F=b' M v F = b ′ M M M t × t t\times t t × t ± 1 \pm1 ± 1 t t t s ( i ) s^{(i)} s ( i ) b ′ ∈ Z t b'\in\mathbb{Z}^t b ′ ∈ Z t t ≤ N + 1 t\le N+1 t ≤ N + 1 t ≤ 1 t\le1 t ≤ 1 v v v k min ( Q ) = 1 k_{\min}(Q)=1 k m i n ( Q ) = 1 t ≥ 2 t\ge2 t ≥ 2
For a square matrix of order ℓ ≥ 1 \ell\ge1 ℓ ≥ 1 ± 1 \pm1 ± 1 { 0 , ± 2 } \{0,\pm2\} { 0 , ± 2 } 2 ℓ − 1 2^{\ell-1} 2 ℓ − 1 v F = adj ( M ) b ′ / det M v_F=\operatorname{adj}(M)b'/\det M v F = adj ( M ) b ′ / det M adj ( M ) \operatorname{adj}(M) adj ( M ) M M M t − 1 t-1 t − 1 2 t − 2 2^{t-2} 2 t − 2 v v v ∣ det M ∣ / 2 t − 2 |\det M|/2^{t-2} ∣ det M ∣/ 2 t − 2 M M M ∣ det M ∣ |\det M| ∣ det M ∣ 1 1 1 ( 1 , 0 , … , 0 ) (1,0,\ldots,0) ( 1 , 0 , … , 0 ) − 2 B ′ -2B' − 2 B ′ B ′ B' B ′ ( t − 1 ) × ( t − 1 ) (t-1)\times(t-1) ( t − 1 ) × ( t − 1 ) { 0 , 1 } \{0,1\} { 0 , 1 } ∣ det M ∣ = 2 t − 1 ∣ det B ′ ∣ |\det M|=2^{t-1}|\det B'| ∣ det M ∣ = 2 t − 1 ∣ det B ′ ∣
k min ( Q ) ≤ ∣ det M ∣ 2 t − 2 = 2 ∣ det B ′ ∣ ≤ 2 Δ ( t − 1 ) ≤ 2 Δ ( N ) , k_{\min}(Q)\le\frac{|\det M|}{2^{t-2}}=2|\det B'|\le2\Delta(t-1)\le2\Delta(N), k m i n ( Q ) ≤ 2 t − 2 ∣ det M ∣ = 2∣ det B ′ ∣ ≤ 2Δ ( t − 1 ) ≤ 2Δ ( N ) , since Δ \Delta Δ 1 1 1 B ′ ′ B'' B ′′ n × n n\times n n × n { 0 , 1 } \{0,1\} { 0 , 1 } M ′ ′ M'' M ′′ n + 1 n+1 n + 1 1 1 1 11 T − 2 B ′ ′ \mathbf{1}\mathbf{1}^{\mathsf T}-2B'' 1 1 T − 2 B ′′ ± 1 \pm1 ± 1 ∣ det M ′ ′ ∣ = 2 n ∣ det B ′ ′ ∣ |\det M''|=2^n|\det B''| ∣ det M ′′ ∣ = 2 n ∣ det B ′′ ∣ ∣ det M ′ ′ ∣ |\det M''| ∣ det M ′′ ∣ ( n + 1 ) ( n + 1 ) / 2 (n+1)^{(n+1)/2} ( n + 1 ) ( n + 1 ) /2 [26 ] ). So Δ ( n ) ≤ ( n + 1 ) ( n + 1 ) / 2 2 − n \Delta(n) \le(n+1)^{(n+1)/2}2^{-n} Δ ( n ) ≤ ( n + 1 ) ( n + 1 ) /2 2 − n
If Q Q Q s ( i ) = − s ( i ′ ) s^{(i)}=-s^{(i')} s ( i ) = − s ( i ′ ) η ( i ′ ) = β − η ( i ′ ) \eta^{(i')}=\beta-\eta^{(i')} η ( i ′ ) = β − η ( i ′ ) β K ≥ 1 \beta_K\ge1 β K ≥ 1 N + 1 N+1 N + 1 ⌊ ( N + 1 ) / 2 ⌋ \lfloor(N+1)/2\rfloor ⌊( N + 1 ) /2 ⌋ M M M M M M t ≤ ⌊ ( N + 1 ) / 2 ⌋ t\le\lfloor(N+1)/2\rfloor t ≤ ⌊( N + 1 ) /2 ⌋ k min ( Q ) ≤ 2 Δ ( t − 1 ) ≤ 2 Δ ( ⌊ ( N − 1 ) / 2 ⌋ ) k_{\min}(Q)\le2\Delta(t-1)\le2\Delta(\lfloor(N-1)/2\rfloor) k m i n ( Q ) ≤ 2Δ ( t − 1 ) ≤ 2Δ (⌊( N − 1 ) /2 ⌋)
The remaining proofs
Proof of Lemma 6.5. On the box ∣ c K − 0 ∣ = c K |c_K-0|=c_K ∣ c K − 0∣ = c K ∣ c K − β K ∣ = β K − c K |c_K-\beta_K|=\beta_K-c_K ∣ c K − β K ∣ = β K − c K (28) . Each coordinate contributes c K c_K c K β K − c K \beta_K-c_K β K − c K
Proof of Lemma 6.8. Compare coefficients on the two sides of (30) . The term S ( J K ) S(J_K) S ( J K ) − ( β K − c K ) − c K = − β K -(\beta_K-c_K)-c_K=-\beta_K − ( β K − c K ) − c K = − β K S ( i ) S(i) S ( i ) S A K 1 \mathrm{SA}^{1}_K SA K 1 i ∈ J K i\in J_K i ∈ J K S A K 2 \mathrm{SA}^{2}_K SA K 2 i ∉ J K i\notin J_K i ∈ / J K ∑ K : i ∈ J K ( β K − c K ) + ∑ K : i ∉ J K c K = ∥ c − η ( i ) ∥ 1 \sum_{K:i\in J_K}(\beta_K-c_K)+\sum_{K:i\notin J_K}c_K=\lVert c-\eta^{(i)}\rVert_1 ∑ K : i ∈ J K ( β K − c K ) + ∑ K : i ∈ / J K c K = ∥ c − η ( i ) ∥ 1 ρ i \rho_i ρ i S ( [ N ] ) S([N]) S ([ N ]) S A K 2 \mathrm{SA}^{2}_K SA K 2 ∑ K c K = ∥ c − η ( O ) ∥ 1 \sum_K c_K=\lVert c-\eta^{(O)}\rVert_1 ∑ K c K = ∥ c − η ( O ) ∥ 1 ρ O \rho_O ρ O 0 ≤ c K ≤ β K 0\le c_K\le\beta_K 0 ≤ c K ≤ β K c ∈ Π ( Q ) c\in\Pi(Q) c ∈ Π ( Q ) k c ∈ Z m kc\in\mathbb{Z}^m k c ∈ Z m k Q kQ k Q (30) are nonnegative integers, and each chain is a sum of instances of subadditivity. □
Appendix C. The inequalities written out
This appendix lists the inequalities that the main text uses but does not print and that no identity in the text fixes, and it compares F 7 F_7 F 7 3 A B C 3ABC 3 A B C 3 S ( A B C ) 3S(ABC) 3 S ( A B C )
The other inequalities of the text are fixed by identities printed there. These are Q 8 ′ = 3 Q 8 − 2 R 8 Q'_8=3Q_8-2R_8 Q 8 ′ = 3 Q 8 − 2 R 8 Q 8 ′ ′ = Q 8 ′ − 3 MMI ( A : H : D E ) Q''_8=Q'_8-3\operatorname{MMI}(A:H:DE) Q 8 ′′ = Q 8 ′ − 3 MMI ( A : H : D E ) R 8 R_8 R 8 (21) for E 1 , … , E 5 E_1,\ldots,E_5 E 1 , … , E 5 6 E 5 = 2 X 7 + Y 7 + 3 μ 5 6E_5=2X_7+Y_7+3\mu_5 6 E 5 = 2 X 7 + Y 7 + 3 μ 5 Y 7 Y_7 Y 7 X 7 X_7 X 7
The summands of Section 5
Besides μ 0 , … , μ 4 \mu_0,\ldots,\mu_4 μ 0 , … , μ 4 (20) , Section 5 uses the orbit sum
μ 5 = MMI ( C : D F : E G ) + MMI ( E : B F : C G ) + MMI ( G : B D : C E ) (46) \mu_5=\operatorname{MMI}(C:DF:EG)+\operatorname{MMI}(E:BF:CG)+\operatorname{MMI}(G:BD:CE) \tag*{(46)} μ 5 = MMI ( C : D F : E G ) + MMI ( E : B F : C G ) + MMI ( G : B D : C E ) (46) and the seven-party inequalities
X 7 : 7 A B C + 7 A D E + 7 A F G + 5 B D F + 5 B D G + 5 B E F + 5 B E G + 5 C D F + 5 C D G + 5 C E F + 6 C E G + 7 A B D F + 7 A B E G + 7 A C D G + 7 A C E F + 4 B C D E + 4 B C F G + 4 D E F G ≥ 4 B + 5 C + 4 D + 5 E + 4 F + 5 G + 4 A B + 3 A C + 4 A D + 3 A E + 4 A F + 3 A G + 3 B C + 4 B D + 4 B E + 4 B F + 4 B G + 4 C D + 4 C E + 4 C F + 4 C G + 3 D E + 4 D F + 4 D G + 4 E F + 4 E G + 3 F G + 5 A B D G + 5 A B E F + 5 A C D F + 6 A C E G + 5 B C D E F G + 7 A B C D E F G , (47) \begin{aligned}
X_7:\quad&7ABC+7ADE+7AFG+5BDF+5BDG+5BEF+5BEG+5CDF+5CDG\\
&+5CEF+6CEG+7ABDF+7ABEG+7ACDG+7ACEF\\
&+4BCDE+4BCFG+4DEFG\\
\ge{}&4B+5C+4D+5E+4F+5G+4AB+3AC+4AD\\
&+3AE+4AF+3AG+3BC+4BD+4BE+4BF+4BG+4CD\\
&+4CE+4CF+4CG+3DE+4DF+4DG+4EF+4EG\\
&+3FG+5ABDG+5ABEF+5ACDF+6ACEG+5BCDEFG+7ABCDEFG, \tag*{(47)}
\end{aligned} X 7 : ≥ 7 A B C + 7 A D E + 7 A F G + 5 B D F + 5 B D G + 5 B E F + 5 B E G + 5 C D F + 5 C D G + 5 C E F + 6 C E G + 7 A B D F + 7 A B E G + 7 A C D G + 7 A C E F + 4 B C D E + 4 B C F G + 4 D E F G 4 B + 5 C + 4 D + 5 E + 4 F + 5 G + 4 A B + 3 A C + 4 A D + 3 A E + 4 A F + 3 A G + 3 B C + 4 B D + 4 B E + 4 B F + 4 B G + 4 C D + 4 C E + 4 C F + 4 C G + 3 D E + 4 D F + 4 D G + 4 E F + 4 E G + 3 F G + 5 A B D G + 5 A B E F + 5 A C D F + 6 A C E G + 5 B C D E F G + 7 A B C D E F G , (47) V 7 : 2 A B C + 2 A D E + 2 A F G + B D F + 2 B D G + 2 B E F + B E G + 2 C D F + C D G + C E F + 2 C E G + 2 A B D F + 2 A B E G + 2 A C D G + 2 A C E F + 3 B C F G + B C D E F + 2 B C D E G + B D E F G + 2 C D E F G ≥ B + 2 C + 3 D + 4 E + F + 2 G + 2 A B + 2 A D + 2 A F + B E + 2 B F + 3 B G + C D + 3 C F + 2 C G + D G + E F + A B D G + A B E F + A C D F + 3 A C E G + B C D E + D E F G + B C D F G + 4 B C D E F G + 2 A B C D E F G (48) V_7:\quad2ABC+2ADE+2AFG+BDF+2BDG+2BEF+BEG
+2CDF+CDG+CEF+2CEG+2ABDF+2ABEG+2ACDG
+2ACEF+3BCFG+BCDEF+2BCDEG+BDEFG+2CDEFG
\ge B+2C+3D+4E+F+2G+2AB+2AD
+2AF+BE+2BF+3BG+CD+3CF+2CG+DG
+EF+ABDG+ABEF+ACDF+3ACEG+BCDE+DEFG+BCDFG
+4BCDEFG+2ABCDEFG \tag*{(48)} V 7 : 2 A B C + 2 A D E + 2 A F G + B D F + 2 B D G + 2 B E F + B E G + 2 C D F + C D G + C E F + 2 C E G + 2 A B D F + 2 A B E G + 2 A C D G + 2 A C E F + 3 B C F G + B C D E F + 2 B C D E G + B D E F G + 2 C D E F G ≥ B + 2 C + 3 D + 4 E + F + 2 G + 2 A B + 2 A D + 2 A F + B E + 2 B F + 3 B G + C D + 3 C F + 2 C G + D G + E F + A B D G + A B E F + A C D F + 3 A C E G + B C D E + D E F G + B C D F G + 4 B C D E F G + 2 A B C D E F G (48) V 7 ′ : 2 A B C + 2 A D E + 2 A F G + B D F + B D G + B E F + B E G + C D F + C D G + C E F + 3 C E G + 2 A B D F + 2 A B E G + 2 A C D G + 2 A C E F + 2 D E F G + B C D E F + B C D E G + 2 B C D F G + 2 B C E F G ≥ 2 B + 4 C + 2 E + F + 3 G + 2 A B + 2 A D + 2 A F + B D + B E + C D + C E + 2 D F + 2 D G + 2 E F + 2 E G + A B D G + A B E F + A C D F + 3 A C E G + 2 B C F G + 4 B C D E F G + 2 A B C D E F G (49) V'_7:\quad2ABC+2ADE+2AFG+BDF+BDG+BEF+BEG
+CDF+CDG+CEF+3CEG+2ABDF+2ABEG+2ACDG
+2ACEF+2DEFG+BCDEF+BCDEG+2BCDFG+2BCEFG
\ge2B+4C+2E+F+3G+2AB+2AD+2AF
+BD+BE+CD+CE+2DF+2DG+2EF+2EG
+ABDG+ABEF+ACDF+3ACEG+2BCFG+4BCDEFG+2ABCDEFG \tag*{(49)} V 7 ′ : 2 A B C + 2 A D E + 2 A F G + B D F + B D G + B E F + B E G + C D F + C D G + C E F + 3 C E G + 2 A B D F + 2 A B E G + 2 A C D G + 2 A C E F + 2 D E F G + B C D E F + B C D E G + 2 B C D F G + 2 B C E F G ≥ 2 B + 4 C + 2 E + F + 3 G + 2 A B + 2 A D + 2 A F + B D + B E + C D + C E + 2 D F + 2 D G + 2 E F + 2 E G + A B D G + A B E F + A C D F + 3 A C E G + 2 B C F G + 4 B C D E F G + 2 A B C D E F G (49) and, for Remark 5.9,
P 7 : 4 A B C + 4 A D E + 4 A F G + 3 B D F + 3 B D G + 3 B E F + 3 B E G + 3 C D F + 3 C D G + 3 C E F + 3 C E G + 4 A B D F + 4 A B E G + 4 A C D G + 4 A C E F + 4 B C D E + 2 B C F G + 2 D E F G ≥ 2 B + 2 C + 2 D + 2 E + 3 F + 3 G + 2 A B + 2 A C + 2 A D + 2 A E + 2 A F + 2 A G + 2 B C + 3 B D + 3 B E + 2 B F + 2 B G + 3 C D + 3 C E + 2 C F + 2 C G + 2 D E + 2 D F + 2 D G + 2 E F + 2 E G + 2 F G + 3 A B D G + 3 A B E F + 3 A C D F + 3 A C E G + B C D E F + B C D E G + 2 B C D E F G + 4 A B C D E F G (50) P_7:\quad4ABC+4ADE+4AFG+3BDF+3BDG+3BEF+3BEG+3CDF+3CDG
+3CEF+3CEG+4ABDF+4ABEG+4ACDG+4ACEF
+4BCDE+2BCFG+2DEFG
\ge2B+2C+2D+2E+3F+3G+2AB+2AC+2AD
+2AE+2AF+2AG+2BC+3BD+3BE+2BF+2BG+3CD
+3CE+2CF+2CG+2DE+2DF+2DG+2EF+2EG
+2FG+3ABDG+3ABEF+3ACDF+3ACEG+BCDEF+BCDEG
+2BCDEFG+4ABCDEFG \tag*{(50)} P 7 : 4 A B C + 4 A D E + 4 A F G + 3 B D F + 3 B D G + 3 B E F + 3 B E G + 3 C D F + 3 C D G + 3 C E F + 3 C E G + 4 A B D F + 4 A B E G + 4 A C D G + 4 A C E F + 4 B C D E + 2 B C F G + 2 D E F G ≥ 2 B + 2 C + 2 D + 2 E + 3 F + 3 G + 2 A B + 2 A C + 2 A D + 2 A E + 2 A F + 2 A G + 2 B C + 3 B D + 3 B E + 2 B F + 2 B G + 3 C D + 3 C E + 2 C F + 2 C G + 2 D E + 2 D F + 2 D G + 2 E F + 2 E G + 2 F G + 3 A B D G + 3 A B E F + 3 A C D F + 3 A C E G + B C D E F + B C D E G + 2 B C D E F G + 4 A B C D E F G (50) The star inequalities of Table 3
The nine-party star inequality of Table 3 without complementary pairs of words is
G 9 : 3 A + 5 B + 5 C + 5 D + 3 E + 4 F + 6 G + 6 H + 4 I + 4 A B C D E F G H I ≥ A B C D G + A B C H I + A B E F G + A C D E F + A C E G H + B C D E H + B C F G H + C D E G I + D F G H I (51) G_9:\quad3A+5B+5C+5D+3E+4F+6G+6H+4I+4ABCDEFGHI
\ge ABCDG+ABCHI+ABEFG+ACDEF+ACEGH
+BCDEH+BCFGH+CDEGI+DFGHI \tag*{(51)} G 9 : 3 A + 5 B + 5 C + 5 D + 3 E + 4 F + 6 G + 6 H + 4 I + 4 A B C D E F G H I ≥ A B C D G + A B C H I + A B E F G + A C D E F + A C E G H + B C D E H + B C F G H + C D E G I + D F G H I (51) With c c c Table 3 , Lemma 6.8 gives 32 G 9 = ∑ K = 1 9 [ ( 32 − 32 c K ) S A K 1 + 32 c K S A K 2 ] 32G_9=\sum_{K=1}^{9}\left[(32-32c_K)SA^1_K+32c_KSA^2_K\right] 32 G 9 = ∑ K = 1 9 [ ( 32 − 32 c K ) S A K 1 + 32 c K S A K 2 ] 32 c = ( 2 , 25 , 28 , 31 , 10 , 8 , 1 , 19 , 4 ) 32c=(2,25,28,31,10,8,1,19,4) 32 c = ( 2 , 25 , 28 , 31 , 10 , 8 , 1 , 19 , 4 )
The inequalities H 9 H_9 H 9 H 11 H_{11} H 11 H 15 H_{15} H 15 H 17 H_{17} H 17 Q T Q_T Q T Theorem 6.14 for the following lists of subsets of [ m ] [m] [ m ] Table 3 and the party i i i 1 T i 1_{T_i} 1 T i
For H 9 H_9 H 9 m = 8 m=8 m = 8
T = { { 5 , 7 , 8 } , { 1 , 2 , 3 , 5 , 7 } , { 2 , 4 , 5 , 8 } , { 1 , 4 , 6 , 7 } , { 1 , 3 , 4 , 8 } , { 2 , 3 , 6 , 7 } , { 1 , 2 , 6 , 8 } , { 3 , 4 , 5 , 6 } } . \mathcal{T}=\{\{5,7,8\},\{1,2,3,5,7\},\{2,4,5,8\},\{1,4,6,7\},\{1,3,4,8\},\{2,3,6,7\},\{1,2,6,8\},\{3,4,5,6\}\}. T = {{ 5 , 7 , 8 } , { 1 , 2 , 3 , 5 , 7 } , { 2 , 4 , 5 , 8 } , { 1 , 4 , 6 , 7 } , { 1 , 3 , 4 , 8 } , { 2 , 3 , 6 , 7 } , { 1 , 2 , 6 , 8 } , { 3 , 4 , 5 , 6 }} . For H 11 H_{11} H 11 m = 8 m=8 m = 8
T = { { 1 , 3 , 4 , 5 , 6 } , { 1 , 2 , 3 , 5 , 7 } , { 1 , 4 , 6 , 7 } , { 2 , 3 , 4 , 8 } , { 2 , 3 , 6 , 7 } , { 1 , 2 , 6 , 8 } , { 2 , 4 , 5 , 7 } , { 3 , 7 , 8 } , { 5 , 6 , 8 } , { 1 , 4 , 5 , 8 } . \mathcal{T}=\{\{1,3,4,5,6\},\{1,2,3,5,7\},\{1,4,6,7\},\{2,3,4,8\},\{2,3,6,7\},\{1,2,6,8\},\{2,4,5,7\},\{3,7,8\},\{5,6,8\},\{1,4,5,8\}. T = {{ 1 , 3 , 4 , 5 , 6 } , { 1 , 2 , 3 , 5 , 7 } , { 1 , 4 , 6 , 7 } , { 2 , 3 , 4 , 8 } , { 2 , 3 , 6 , 7 } , { 1 , 2 , 6 , 8 } , { 2 , 4 , 5 , 7 } , { 3 , 7 , 8 } , { 5 , 6 , 8 } , { 1 , 4 , 5 , 8 } . In both lists every coin lies in exactly half of the sets, so (W2) holds with all γ i = 1 \gamma_i=1 γ i = 1 H 15 H_{15} H 15 m = 8 m=8 m = 8 T = ( T 1 , … , T 7 , T ‾ 1 , … , T ‾ 7 ) \mathcal{T}=(T_1,\ldots,T_7,\overline{T}_1,\ldots,\overline{T}_7) T = ( T 1 , … , T 7 , T 1 , … , T 7 )
( T 1 , … , T 7 ) = { { 3 , 7 , 8 } , { 4 , 6 , 8 } , { 2 , 3 , 5 , 8 } , { 5 , 6 , 7 } , { 2 , 3 , 6 , 7 } , { 2 , 4 , 5 , 7 } , { 3 , 4 , 5 , 6 } } . (T_1,\ldots,T_7)=\{\{3,7,8\},\{4,6,8\},\{2,3,5,8\},\{5,6,7\},\{2,3,6,7\},\{2,4,5,7\},\{3,4,5,6\}\}. ( T 1 , … , T 7 ) = {{ 3 , 7 , 8 } , { 4 , 6 , 8 } , { 2 , 3 , 5 , 8 } , { 5 , 6 , 7 } , { 2 , 3 , 6 , 7 } , { 2 , 4 , 5 , 7 } , { 3 , 4 , 5 , 6 }} . For H 17 H_{17} H 17 m = 9 m=9 m = 9 T = ( T 1 , … , T 8 , T ˉ 1 , … , T ˉ 8 ) \mathcal{T}=(T_1,\ldots,T_8,\bar{T}_1,\ldots,\bar{T}_8) T = ( T 1 , … , T 8 , T ˉ 1 , … , T ˉ 8 )
( T 1 , … , T 8 ) = { { 2 , 3 , 4 , 8 } , { 3 , 4 , 5 , 6 } , { 2 , 4 , 6 , 7 } , { 2 , 3 , 5 , 7 } , { 3 , 4 , 6 , 8 , 9 } , { 2 , 4 , 5 , 7 , 9 } , { 2 , 3 , 5 , 6 , 9 } , { 3 , 4 , 7 , 9 } } , (T_1,\ldots,T_8)=\{\{2,3,4,8\},\{3,4,5,6\},\{2,4,6,7\},\{2,3,5,7\},\{3,4,6,8,9\},\{2,4,5,7,9\},\{2,3,5,6,9\},\{3,4,7,9\}\}, ( T 1 , … , T 8 ) = {{ 2 , 3 , 4 , 8 } , { 3 , 4 , 5 , 6 } , { 2 , 4 , 6 , 7 } , { 2 , 3 , 5 , 7 } , { 3 , 4 , 6 , 8 , 9 } , { 2 , 4 , 5 , 7 , 9 } , { 2 , 3 , 5 , 6 , 9 } , { 3 , 4 , 7 , 9 }} , the rows of an 8 × 9 8 \times9 8 × 9 [26 ] , read as weighings as in the proof of Corollary 6.22 . In each case the vector ω \omega ω q q q Table 3 .
Seven-party inequalities compared with F7
Members of the toric, projective-plane and cyclic families with more than seven parties give seven-party inequalities when parties are merged or deleted. Both operations keep every coefficient on its side and can only combine, cancel or remove terms, so they do not increase ∣ α ∣ |\alpha| ∣ α ∣ ∣ β ∣ |\beta| ∣ β ∣ F 7 F_7 F 7 ∣ α ∣ ≥ 39 |\alpha| \ge39 ∣ α ∣ ≥ 39 ∣ β ∣ ≥ 54 |\beta| \ge54 ∣ β ∣ ≥ 54 ∣ β ∣ ≤ 50 |\beta| \le50 ∣ β ∣ ≤ 50 ∣ α ∣ < 39 |\alpha| < 39 ∣ α ∣ < 39 F 7 F_7 F 7
The table contains every seven-party inequality that we found in the works on holographic entropy inequalities cited here and in the papers that cite [30 , 8 , 40 , 41 ] , screened by their abstracts. We did not compare F 7 F_7 F 7 [40 ] , whose seven-party instances are not written out there, with the averaged inequalities of the symmetrized cones [42 , 43 ] , which constrain only sums over relabelings, with family members with more than 14 parties, or with works outside this search. We found no published list of facets of HEC7. The facet property of the seven-party members of the toric and projective-plane families was shown in [9 ] .
