On Boolean polynomials and the Union-Closed Conjecture

Mario DeFranco · 2026

Read On Boolean polynomials and the Union-Closed Conjecture by Mario DeFranco (2026) in the Tower of Babel, a free online library of public-domain works preserved in clean, searchable text. No sign-up. The full text is served as a plain-text file at a predictable URL, where text is present: https://antarctic-labs.com/tower-of-babel/arxiv-2606-26191.txt.

Introduction

Mario DeFranco recasts a famous open problem in combinatorics as a question about one polynomial. The Union-Closed Conjecture, also called Frankl's conjecture, concerns families of sets closed under unions. It claims some element belongs to at least half the sets. DeFranco works with the equivalent Intersection-Closed version instead. Sets and membership get encoded as vectors over the two-element field. Characteristic functions then capture the conjecture's premises and conclusion.

Construction of the polynomial is the core move. For set counts m and universe size n, his Boolean polynomial vanishes exactly when the conjecture holds for those parameters. Formulas for the ingredient polynomials are proved along the way. The reformulation does not settle the conjecture. It converts a statement about all set families into an algebraic identity check. Such translations sometimes crack old problems. Boolean algebra now holds a complete copy of this one.

Catalog record

CREATORMario DeFranco
YEAR2026
COLLECTIONPAPERS
FORMATTXT
FILE SIZE12 KB
LICENSEhttp://creativecommons.org/licenses/by/4.0/
RIGHTSCC BY
SOURCEarXiv

Source: https://arxiv.org/abs/2606.26191

Browse the full library · About the Tower of Babel

Full text

The opening of the work, from the library's hosted text:

On Boolean polynomials and the Union-Closed Conjecture Mario DeFranco Abstract For a set of m m subsets of a universe set of size n n , we construct a Boolean polynomial ICC m , n ​ ( X ) \mathrm{ICC}_{m,n}(X) such that the Union-Closed Conjecture is true for this m m and n n if and only if ICC m , n ​ ( X ) \mathrm{ICC}_{m,n}(X) is the zero Boolean polynomial. We use an equivalent formulation, called the Intersection-Closed Conjecture. 1 Introduction Fix integers m and n both greater than 1. Let [1,n] denote the set of integers \{j\colon 1\leq i\leq n\} , and suppose we have m distinct sets A_{i}\subset[1,n],1\leq i\leq m . Let A denote the set of these sets: A=\{A_{i}\colon 1\leq i\leq m\}. Also suppose that A is union-closed, i.e. A_{i_{1}}\cup A_{i_{2}}\in A for any pair 1\leq i_{1}<i_{2}\leq m . Then the Union-Closed Conjecture states that there exists some j\in[1,n] such that \#\{i\colon j\in A_{i}\}\geq\lceil\frac{m}{2}\rceil. See [ 1 ] for a history of this conjecture up to 2013. It is also known as Frankl’s Conjecture. In this paper, we consider the Intersection-Closed Conjecture, a well-known equivalent formulation; instead of A being union-closed, suppose that it is intersection-closed, i.e. A_{i_{1}}\cap A_{i_{2}}\in A for any pair 1\leq i_{1}<i_{2}\leq m . Then the Intersection-Closed Conjecture (statement ICC (m,n) ) states that there exists some j\in[1,n] such that \#\{i\colon j\in A_{i}\}\leq\lfloor\frac{m}{2}\rfloor. In Section 2, we define a Boolean polynomial \mathrm{ICC}_{m,n}(X) such that statement ICC (m,n) is equivalent to this polynomial being the zero Boolean polynomial. Our approach is use the standard encoding of sets as elements in \mathbb{F}_{2}^{n} and then to construct characteristic functions for the premises and conclusion of the conjecture. In Section 3, we prove some formulas for certain Boolean polynomials used in our construction. In Section 4, we mention some other problems which can similarly formulated using Boolean polynomials. We note that the paper [ 2 ] phrases the sets A_{i} in terms of Boolean functions, but does not construct the characteristic functions of various properties of the sets as done in Section 2 here. 2 The Boolean polynomial \mathrm{ICC}_{m,n}(X) Definition 1 . Fix integers m,n\geq 2 . Consider a set of mn Boolean variables \{x_{i,j}:1\leq i\leq m;1\leq j\leq n\}, i.e. x_{i,j}^{2}=x_{i,j} . Let X_{i} denote the sequence X_{i}=(x_{i,1},\ldots,x_{i,n}). Let B denote the Boolean algebra B=\mathbb{F}_{2}[\{x_{i,j}\}_{i,j}]. For each specialization S of Boolean variables to values in \mathbb{F}_{2} , each sequence X_{i} corresponds to a subset of \{1,\ldots,n\} , so we will denote such a set by X_{i}|_{S} . We will also let u_{j},v_{j} for 1\leq j\leq n denote Boolean variables, and we will denote specializations of u_{j},v_{j} to \mathbb{F}_{2} by S also. We will call any polynomial of Boolean variables with coefficients in \mathbb{F}_{2} a “Boolean polynomial” . Definition 2 . For the variables u=(u_{j})_{j=1}^{n},v=(v_{j})_{j=1}^{n} , define the Boolean polynomial \mathrm{PairwiseDistinct}(u,v) \mathrm{PairwiseDistinct}(u,v)=1+\prod_{j=1}^{n}(1+u_{j}+v_{j}). Then the sets u|_{S} and v|_{S} are distinct if and only if \mathrm{PairwiseDistinct}(u,v)|_{S}=1. Definition 3 . Define \mathrm{Distinct}(X)\in B by \mathrm{Distinct}(X)=\prod_{1\leq i_{1}<i_{2}\leq m}\mathrm{PairwiseDistinct}(X_{i_{1}},X_{i_{2}}). Definition 4 . A set u|_{S} is a member of the set X|_{S} if and only if \prod_{i=1}^{m}\mathrm{PairwiseDistinct}(u,X_{i})|_{S}=0. Define \mathrm{Member}(X,u) by \mathrm{Member}(X,u)=1+\prod_{i=1}^{m}\mathrm{PairwiseDistinct}(u,X_{i}) Definition 5 . Define the sequence u\cap v u\cap v=(u_{j}v_{j})_{j=1}^{n} Thus define the Boolean polynomial \mathrm{IntersectionClosed}(X) by \mathrm{IntersectionClosed}(X)=\prod_{1\leq i_{1}<i_{2}\leq m}\mathrm{Member}(X,X_{i_{1}}\cap X_{i_{2}}) Therefore the set X|_{S} is intersection-closed if and only if \mathrm{IntersectionClosed}(X)|_{S}=1. Definition 6 . Define a matching on the set [1,2k] to be a set partition of [1,2k] with each set having size 2. Define a matching on the set [1,2k+1] to be a set partition of [1,2k+1] with one set of size 1 and all other sets of size 2. Let \mathrm{Matchings}(m) denote the set of all matchings of [1,m] . For M\in\mathrm{Matchings}(m) , define H_{M,j}(X)=\begin{cases}\prod_{\{i_{1},i_{2}\}\in M}(1+x_{i_{1},j}x_{i_{2},j})&\text{ if $m$ is even}\\ (1+x_{i_{0},j})\prod_{\{i_{1},i_{2}\}\in M}(1+x_{i_{1},j}x_{i_{2},j})&\text{ if $m$ is odd}\end{cases} where \{i_{0}\} is the unique set of size 1 in M , if m is odd. For a specialization S of X and integer j,1\leq j\leq n , define the statement H(S,j) to be: \#\{i\colon j\in X_{i}|_{S}\}\leq\lfloor\frac{m}{2}\rfloor where m is the number of sets in the set X|_{S} . Remark 1 . If statement H (S,j) is true, then there exists some matching M of [1,m] such that H_{M,j}(X)|_{S}=1. Thus if statement H(S,j) is true, then \prod_{M\in\mathrm{Matchings}(m)}(1+H_{M,j}(X))|_{S}=0. Definition 7 . Define \mathrm{HalfMembership}(X)=\prod_{j=1}^{n}\prod_{M\in\mathrm{Matchings}(m)}(1+H_{M,j}(X)). Definition 8 . Let \mathrm{Specializations}_{\mathrm{ICC}}(m,n) denote the set of specializations S of the variables x_{i,j} such that the set X|_{S} is an intersection-closed set of distinct sets. Define the statement \mathrm{ICC}(m,n) to be “For a specialization S\in\mathrm{Specializations}_{\mathrm{ICC}}(m,n) , there exists some integer j such that \#\{i\colon j\in X_{j}|_{S}\}\leq\lfloor\frac{m}{2}\rfloor. Theorem 1 . Statement \mathrm{ICC}(m,n) is true if and only if \mathrm{ICC}_{m,n}(X) is the zoo Boolean polynomial. Proof. If the statement ICC (m,n) is true, then for any S\in\mathrm{Specializations}_{\mathrm{ICC}}(m,n) . we have \displaystyle\mathrm{Distinct}(X)|_{S} \displaystyle=1 \displaystyle\mathrm{IntersectionClosed}(X)|_{S} \displaystyle=1 \displaystyle\mathrm{HalfMembership}(X)|_{S} \displaystyle=0. And if S\notin\mathrm{Specializations}_{\mathrm{ICC}}(m,n) , then either \mathrm{Distinct}(X)|_{S}=0\text{ or }\mathrm{IntersectionClosed}(X)|_{S}=0. So, if statement ICC (m,n) is true, then the polynomial \mathrm{ICC}_{m,n}(X)=\mathrm{Distinct}(X)\mathrm{IntersectionClosed}(X)\mathrm{HalfMembership}(X) evaluates to 0 for all specializations S , and thus must be the zero Boolean polynomial. Conversely, suppose \mathrm{ICC}_{m,n}(X) is the zero Boolean polynomial. Then for S\in\mathrm{Specializations}_{\mathrm{ICC}}(m,n) , we know \mathrm{Distinct}(X)|_{S}=\mathrm{IntersectionClosed}(X)|_{S}=1, so must have \mathrm{HalfMembership}(X)|_{S}=0. Thus H_{M,j}(X)|_{S}=1 for some M and j , which implies that the element j is in at most \lfloor\frac{m}{2}\rfloor sets of X|_{S} . Thus the statement ICC (m,n) is true if and only if \mathrm{ICC}_{m,n}(X) is the zero Boolean polynomial. This completes the proof. ∎ 3 Formulas for Member (X,u) and Member (X,u) PairwiseDistinct (u,v) Definition 9 . For a set W\subset\mathbb{Z} , let 2^{W} the set of subsets of W , and let (2^{W})^{\prime} denote the set of non-empty subsets of W . For integer k\geq 0 , let {W\choose k} denote the set of subsets of W of size k , which we write as ordered k -tuples (i_{1},\ldots,i_{k}). Ket W^{c} denote the complement of W in [1,n] . For a set V of Boolean variables, let e_{r}(V) denote the r -th elementary symmetric polynomial on these variables. Lemma 1 . \displaystyle\mathrm{Member}(X,u)= \displaystyle\prod_{j=1}^{n}(1+u_{j}) \displaystyle+\sum_{k=1}^{m-1}\sum_{(i_{1},\ldots,i_{k})\in{[1,n]\choose k}}\sum_{(W_{i_{1}},\ldots,W_{i_{k}})\in((2^{[1,n]})^{\prime})^{k}}F(\cap_{l=1}^{k}W_{i_{l}}))\prod_{l=1}^{k}\prod_{j\in W_{i_{l}}}x_{i_{l},j} \displaystyle+\sum_{(W_{1},\ldots,W_{m})\in((2^{[1,n]})^{\prime})^{m}}(\prod_{j\in(\cap_{l=1}^{m}W_{l})^{c}}(1+u_{j}))\prod_{l=1}^{m}\prod_{j\in W_{l}}x_{l,j} where for any set W\subset[1,n] , \displaystyle F(W)=(\prod_{j\in W^{c}}(1+u_{j}))\sum_{r=1}^{|W|}e_{r}(\{u_{j}\colon j\in W\})) Proof. By definition \displaystyle\mathrm{Member}(X,u) \displaystyle=1+\prod_{i=1}^{m}(1+\prod_{j=1}^{n}(1+u_{j}+x_{i,j})) \displaystyle=1+\prod_{i=1}^{m}(1+\sum_{W\subset[1,n]}(\prod_{j\in W}x_{i,j})\prod_{j\in W^{c}}(1+u_{j})) \displaystyle=1+1+\sum_{k=1}^{m}\sum_{(i_{1},\ldots,i_{k})\in{[1,n]\choose k}}\sum_{(W_{i_{1}},\ldots,W_{i_{k}})\in({2^{[1,n]}})^{k}}\prod_{l=1}^{k}(\prod_{j\in W_{i_{l}}}x_{i_{l},j})\prod_{j\in W_{i_{l}}^{c}}(1+u_{j}). In the sum over index k , at k equal to some k_{0}<m , fix some index \vec{i}=(i_{1},\ldots,i_{k_{0}}) and then some index \vec{W}=(W_{i_{1}},\ldots,W_{i_{k_{0}}}) such that each of these sets W_{i_{l}} is non-empty. The contribution from this triple (k_{0},\vec{i},\vec{W}) is \displaystyle\prod_{l=1}^{k_{0}}(\prod_{j\in W_{i_{l}}}x_{i_{l},j}\prod_{j\in W_{i_{l}}^{c}}(1+u_{j})) \displaystyle= \displaystyle(\prod_{l=1}^{k_{0}}\prod_{j\in W_{i_{l}}}x_{i_{l},j})\prod_{j\in\cup_{l=1}^{k_{0}}W_{i_{l}}^{c}}(1+u_{j}) \displaystyle= \displaystyle(\prod_{l=1}^{k_{0}}\prod_{j\in W_{i_{l}}}x_{i_{l},j})\prod_{j\in(\cap_{l=1}^{k_{0}}W_{i_{l}})^{c}}(1+u_{j}) The only other terms that have this same factor of the variables x_{i,j} come from terms with k=k_{1}>k_{0} with indices (i_{1}^{\prime},\ldots,i_{k_{1}}^{\prime}) and (W_{i_{1}^{\prime}},\ldots,W_{i_{k_{1}}^{\prime}}) such that each i_{l} is equal to some i_{l^{\prime}}^{\prime} with W_{i_{l}}=W_{i_{l^{\prime}}^{\prime}} , and the remaining W_{i_{l}^{\prime}} are empty. Since k_{1}>k_{0} , at least one of these sets is empty, so the u -contribution is \prod_{j=1}^{n}(1+u_{j}). Summing over all such k_{1} and counting the corresponding indices gives the u -contribution \displaystyle\prod_{j=1}^{n}(1+u_{j})\sum_{k=k_{0}+1}^{m}{m-k_{0}\choose k-k_{0}} \displaystyle= \displaystyle\prod_{j=1}^{n}(1+u_{j})(2^{m-k_{0}}-1) \displaystyle= \displaystyle\prod_{j=1}^{n}(1+u_{j}) because m>k_{0} . Thus the u -coefficient of this x -product is (\prod_{j\in(\cap_{l=1}^{k_{0}}W_{i_{l}})^{c}}(1+u_{j}))+\prod_{j=1}^{n}(1+u_{j}). Factoring the above expression gives the stated form of F(\cap_{l=1}^{k_{0}}W_{i_{l}}) . In the sum over k , the terms with W_{i_{l}} all empty contribute \displaystyle\prod_{j=1}^{n}(1+u_{j})\sum_{k=1}^{m}{m\choose k} \displaystyle= \displaystyle\prod_{j=1}^{n}(1+u_{j})(2^{m}-1) \displaystyle= \displaystyle\prod_{j=1}^{n}(1+u_{j}). This completes the proof. ∎ Lemma

Read the complete text