EPFL, Switzerland<EMAIL_ADDRESS>University of Oxford, UK
<EMAIL_ADDRESS>EPFL, Switzerland<EMAIL_ADDRESS>Mika Göös,
Stefan Kiefer, and Weiqiang Yuan <ccs2012> <concept>
<concept_id>10003752.10003766.10003776</concept_id> <concept_desc>Theory of
computation Regular languages</concept_desc>
<concept_significance>500</concept_significance> </concept> <concept>
<concept_id>10003752.10003777.10003780</concept_id> <concept_desc>Theory of
computation Communication complexity</concept_desc>
<concept_significance>500</concept_significance> </concept> </ccs2012>
[500]Theory of computation Regular languages John Q. Open and Joan R. Access 2
42nd Conference on Very Important Topics (CVIT 2016) CVIT 2016 CVIT 2016
December 24–27, 2016 Little Whinging, United Kingdom 42 23
[name=Fact,sibling=theorem]fact [name=Question,sibling=theorem]question

# Lower Bounds for Unambiguous Automata
via Communication Complexity

Mika Göös  Stefan Kiefer  Weiqiang Yuan

###### Abstract

We use results from communication complexity, both new and old ones, to prove
lower bounds for unambiguous finite automata (UFAs). We show three results.

  1. 1.

_Complement:_ There is a language $L$ recognised by an $n$-state UFA such that
the complement language $\overline{L}$ requires NFAs with
$n^{\tilde{\Omega}(\log n)}$ states. This improves on a lower bound by Raskin.

  2. 2.

_Union:_ There are languages $L_{1}$, $L_{2}$ recognised by $n$-state UFAs
such that the union $L_{1}\cup L_{2}$ requires UFAs with
$n^{\tilde{\Omega}(\log n)}$ states.

  3. 3.

_Separation:_ There is a language $L$ such that both $L$ and $\overline{L}$
are recognised by $n$-state NFAs but such that $L$ requires UFAs with
$n^{\Omega(\log n)}$ states. This refutes a conjecture by Colcombet.

###### keywords:

Unambiguous automata, communication complexity

###### category:

##  1 Introduction

Given two finite automata recognising languages
$L_{1},L_{2}\subseteq\Sigma^{*}$ a basic question is to determine the _state
complexity_ of various language operations. How many states are needed in an
automaton that recognises the union $L_{1}\cup L_{2}$? How about the
intersection $L_{1}\cap L_{2}$? The complement
$\overline{L}_{1}\coloneqq\Sigma^{*}\setminus L_{1}$? The answer depends on
the type of automaton considered, such as deterministic (DFA),
nondeterministic (NFA), or unambiguous (UFA). Recall that a UFA is an NFA that
has at most one accepting computation on any input.

State complexities have been extensively studied for various types of automata
and language operations; see, e.g., [9, 15] and their references, or the
excellent compendium on Wikipedia [22]. For example, complementing an NFA with
$n$ states may require $2^{n}$ states [3], even for automata with binary
alphabet [14]. Surprisingly, several extremely basic questions about UFAs
remain open. For example, it was shown only in 2018 by Raskin [20] that the
state complexity for UFA complementation is not polynomial: for any
$n\in\mathbb{N}$ there exists a language $L$ recognised by an $n$-state UFA
such that any UFA (or even NFA) that recognises $\overline{L}$ has at least
$n^{(\log\log\log n)^{\Omega(1)}}$ states. This superpolynomial blowup refuted
a conjecture that it may be possible to complement UFAs with a polynomial
blowup [5].

In this paper, as our main results, we prove three new blowup theorems.

######  Theorem 1.1 (Complement).

For every $n\in\mathbb{N}$ there is a language $L\subseteq\\{0,1\\}^{*}$
recognised by an $n$-state UFA such that any NFA that recognises
$\overline{L}$ requires $n^{\tilde{\Omega}(\log n)}$ states.

######  Theorem 1.2 (Union).

For every $n\in\mathbb{N}$ there are languages
$L_{1},L_{2}\subseteq\\{0,1\\}^{*}$ recognised by $n$-state UFAs such that any
UFA that recognises $L_{1}\cup L_{2}$ requires $n^{\tilde{\Omega}(\log n)}$
states.

######  Theorem 1.3 (Separation).

For every $n\in\mathbb{N}$ there is a language $L\subseteq\\{0,1\\}^{*}$ such
that both $L$ and $\overline{L}$ are recognised by $n$-state NFAs but any UFA
that recognises $L$ requires $n^{\Omega(\log n)}$ states.

#### Discussion of main results.

Theorem 1.1 upgrades Raskin’s slightly-superpolynomial bound into a
quasipolynomial bound $n^{\tilde{\Omega}(\log n)}$. (Here we use the notation
$\tilde{\Omega}(m)$ to suppress $\mathrm{poly}(\log m)$ factors.) However, we
note that Raskin’s language is unary, $|\Sigma|=1$, while ours is binary,
$|\Sigma|=2$, and hence the two results are incomparable in this sense. As for
positive results, it is known that the trivial $2^{n}$ upper bound for UFA
complementation can be improved: the complement of any $n$-state UFA can be
recognised by a UFA with at most $\mathrm{poly}(n)\cdot 2^{n/2}$ states [15,
13]. Closing the exponential gap here between the lower and upper bounds
remains a tantalising open problem. It was highlighted as one of the foremost
challenges in the recent Dagstuhl workshop _Unambiguity in Automata Theory_
[6].

Theorem 1.2 establishes the first superpolynomial lower bound for the union
operation. Letting $\sqcup$ denote disjoint union, observe that

$L_{1}\cup L_{2}\leavevmode\nobreak\ =\leavevmode\nobreak\
L_{1}\sqcup(L_{2}\cap\overline{L}_{1}).$ (1)

Since disjoint union and intersection are polynomial for UFAs, it follows from
1 and Theorem 1.2 that the same $n^{\tilde{\Omega}(\log n)}$ lower bound holds
for complementing UFAs. However, we stress that Theorem 1.1 has a stronger
conclusion than this, since it proves a lower bound against NFAs, not just
UFAs. The observation 1 also yields the upper bound $\mathrm{poly}(n)\cdot
2^{n/2}$ by using the complement construction from [15, 13].

Theorem 1.3 refutes a conjecture by Colcombet [5, Conjecture 2]. Indeed, he
conjectured that for any pair of NFAs recognising languages $L_{1}$, $L_{2}$
such that $L_{1}\cap L_{2}=\emptyset$, there is a polynomial-sized UFA that
recognises some $L$ that _separates_ $L_{1}$ and $L_{2}$ in the sense that
$L_{1}\subseteq L$ and $L\cap L_{2}=\emptyset$. Theorem 1.3 refutes this even
in the special case $L_{1}=\overline{L}_{2}$. Related separability questions
are classical in formal language theory and have attracted renewed attention;
see, e.g, [8] and the references therein. Separating automata have also been
used recently to elegantly describe quasipolynomial time algorithms for
solving parity games in an automata theoretic framework; see [4, Chapter 3]
and [7].

###  1.1 Technique: Communication complexity

Our three main theorems rely on results—both new and old—in communication
complexity; see [18, 19] for the standard textbooks. In communication
complexity, one studies functions of the form
$F\colon\\{0,1\\}^{n}\times\\{0,1\\}^{n}\to\\{0,1\\}$ that determine the
following two-party communication problem: Alice holds $x\in\\{0,1\\}^{n}$,
Bob holds $y\in\\{0,1\\}^{n}$, and their goal is to output $F(x,y)$ while
communicating as few bits as possible between them. Communication complexity
is a classical tool to prove lower bounds for automata. Indeed, it is well
known that if the language $\\{xy:F(x,y)=1\\}$ is recognised by a small DFA
(resp. NFA, UFA) then $F$ admits an efficient deterministic (resp.
nondeterministic, unambiguous) protocol. We revisit this connection in light
of recent developments in communication complexity.

Theorem 1.1 is a _relatively straightforward consequence_ of a recent result
of Balodis et al. [2]. They exhibited a two-party function whose co-
nondeterministic communication complexity is nearly quadratic in its
unambiguous complexity (which matches an upper bound due to Yannakakis [23]).
We translate this separation into the language of automata theory, virtually
in a black-box fashion.

Theorem 1.2, by contrast, is our _main technical contribution_. We will show
that it follows from the following analogous communication result, which we
prove in this paper.

######  Theorem 1.4.

For every $m\in\mathbb{N}$ there exists a function $F(x,y)$ with unambiguous
communication complexity at most $m$ such that the logical-or of two copies of
$F$, namely, $F^{\lor}(xx^{\prime},yy^{\prime})\coloneqq F(x,y)\lor
F(x^{\prime},y^{\prime})$, has unambiguous communication complexity
$\tilde{\Omega}(m^{2})$.

This is a new result in communication complexity; the unambiguous complexity
of $F^{\lor}$ has not been studied previously. We prove Theorem 1.4 using the
popular _query-to-communication lifting_ technique that has been wildly
successful in the past decade to prove communication lower bounds (including
in [2]). In this technique, one starts by proving a lower bound on the query
(aka decision tree) complexity of a boolean function
$f\colon\\{0,1\\}^{n}\to\\{0,1\\}$. A lifting theorem (e.g., [12]) then
transforms $f$ into an analogous communication problem $F$ in such a way that
the communication complexity of $F$ is characterised by the query complexity
of $f$. This reduces the task of proving communication lower bounds into the
much easier task of proving query lower bounds.

Interestingly, our proof of Theorem 1.4 formalises a kind of _converse_ to the
observation 1 above (saying that union can be computed via a complement).
Namely, we show that unambiguously computing the union necessarily requires
computing a complement, and therefore we can rely on an existing query lower
bound for complementation [11].

Theorem 1.3, finally, is a straightforward consequence of a classical
quadratic separation between two-sided nondeterministic communication
complexity and unambiguous communication complexity due to Razborov [21].

###  1.2 Bonus result: Approximate nonnegative rank

Along the way to Theorem 1.4 we inadvertently stumbled upon another separation
result that addresses a question raised by Kol et al. [16]. They studied the
_$\epsilon$ -approximate nonnegative rank_ $\mathrm{rk}_{\epsilon}^{+}(M)$ of
a nonnegative matrix $M\in\mathbb{R}^{n\times n}$. Here,
$\mathrm{rk}_{\epsilon}^{+}(M)$ is defined as the least nonnegative rank
$\mathrm{rk}^{+}(N)$ of a matrix $N\in\mathbb{R}^{n\times n}$ such that
$|M_{ij}-N_{ij}|\leq\epsilon$ for all $i,j$; see Section 3 for precise
definitions. In particular, Kol et al. [16] asked whether for all error
parameters $0<\epsilon<\delta<1/2$ and boolean matrices
$M\in\\{0,1\\}^{n\times n}$ we have the polynomial relationship
$\mathrm{rk}_{\epsilon}^{+}(M)\leq O(\mathrm{rk}_{\delta}^{+}(M)^{C})$ where
$C=C(\epsilon,\delta)$ is a constant. In short, does approximate nonnegative
rank admit efficient error reduction? (It is known that the more usual notion,
_approximate rank_ , does [1].) We provide the following negative answer.

######  Theorem 1.5 (No efficient error reduction).

For every $m\in\mathbb{N}$ there exists a boolean matrix $M$ with
$\mathrm{rk}_{1/4}^{+}(M)\leq m$ but such that
$\mathrm{rk}_{10^{-5}}^{+}(M)\geq m^{\tilde{\Omega}(\log m)}$.

Previously, a negative answer was known only for _partial_ boolean matrices
$M\in\\{0,1,*\\}^{n\times n}$ that allow “don’t care” entries $M_{ij}=*$ [12].
Our Theorem 1.5 still leaves open the possibility (also raised by [16]) that,
for a total boolean matrix $M$, we can bound $\mathrm{rk}_{\epsilon}^{+}(M)$
as a polynomial function of
$\mathrm{rk}_{\delta}^{+}(M)+\mathrm{rk}_{\delta}^{+}(\overline{M})$ where
$\overline{M}$ is the boolean complement.

###  1.3 Open problems

Our quasipolynomial lower bounds for automata are not known to be tight; in
all cases the best known upper bounds are exponential. Curiously enough, the
analogous communication results are tight for communication protocols. This
suggests two opportunities.

  * •

Can other techniques from communication complexity improve the lower bounds
further? Perhaps via multi-party communication complexity?

  * •

Can techniques for proving upper bounds on communication complexity be adapted
to prove upper bounds on the size of automata?

###  1.4 Definitions of automata

An _NFA_ is a quintuple $\mathcal{A}=(Q,\Sigma,\delta,I,F)$, where $Q$ is the
finite set of states, $\Sigma$ is the finite alphabet, $\delta\subseteq
Q\times\Sigma\times Q$ is the transition relation, $I\subseteq Q$ is the set
of initial states, and $F\subseteq Q$ is the set of accepting states. We write
$q\xrightarrow{a}r$ to denote that $(q,a,r)\in\delta$. A finite sequence
$q_{0}\xrightarrow{a_{1}}q_{1}\xrightarrow{a_{2}}\cdots\xrightarrow{a_{n}}q_{n}$
is called a _run_ ; it can be summarized as $q_{0}\xrightarrow{a_{1}\cdots
a_{n}}q_{n}$. The NFA $\mathcal{A}$ _recognizes_ the language
$L(\mathcal{A}):=\\{w\in\Sigma^{*}\mid\exists\,q_{0}\in I\,.\,\exists\,f\in
F\,.\,q_{0}\xrightarrow{w}f\\}$. The NFA $\mathcal{A}$ is a _DFA_ if $|I|=1$
and for every $q\in Q$ and $a\in\Sigma$ there is exactly one $q^{\prime}$ with
$q\xrightarrow{a}q^{\prime}$. The NFA $\mathcal{A}$ is a _UFA_ if for every
word $w=a_{1}\cdots a_{n}\in\Sigma^{*}$ there is at most one _accepting_ run
for $w$, i.e., a run
$q_{0}\xrightarrow{a_{1}}q_{1}\xrightarrow{a_{2}}\cdots\xrightarrow{a_{n}}q_{n}$
with $q_{0}\in I$ and $q_{n}\in F$. Any DFA is a UFA.

##  2 UFA Complementation

In this section we prove Theorem 1.1. See 1.1 The proof uses concepts from
communication complexity, in particular a recent result from [2] and a
nondeterministic lifting theorem from [12]. We start by recalling these tools.

###  2.1 DNFs and nondeterministic protocols

#### Unambiguous DNFs.

Let $D=C_{1}\lor\cdots\lor C_{m}$ be an $n$-variate boolean formula in
disjunctive normal form (DNF). DNF $D$ has _width_ $k$ if every $C_{i}$ is a
conjunction of at most $k$ literals. We call such $D$ a _$k$ -DNF_. For
conjunctive normal form (CNF) formulas the width and $k$-CNFs are defined
analogously. DNF $D$ is said to be _unambiguous_ if for every input
$x\in\\{0,1\\}^{n}$ at most one of the conjunctions $C_{i}$ evaluates to true,
$C_{i}(x)=1$. For any boolean function $f\colon\\{0,1\\}^{n}\to\\{0,1\\}$
define

  * •

$\mathrm{C}_{1}(f)$ as the least $k$ such that $f$ can be written as a
$k$-DNF;

  * •

$\mathrm{C}_{0}(f)$ as the least $k$ such that $f$ can be written as a
$k$-CNF;

  * •

$\mathrm{UC}_{1}(f)$ as the least $k$ such that $f$ can be written as an
unambiguous $k$-DNF.

Note that $\mathrm{C}_{0}(f)=\mathrm{C}_{1}(\neg f)$. The following recent
result separates two of these measures.

######  Theorem 2.1 ([2, Theorem 1]).

For every $k\in\mathbb{N}$ there exists a function
$f\colon\\{0,1\\}^{n}\to\\{0,1\\}$ where $n\leq\mathrm{poly}(k)$ and such that
$\mathrm{UC}_{1}(f)\leq k$ and $\mathrm{C}_{0}(f)\geq\tilde{\Omega}(k^{2})$.∎

In words, for every $k$ there is an unambiguous $k$-DNF such that any
equivalent CNF requires width $\tilde{\Omega}(k^{2})$. The bound is almost
tight, as every unambiguous $k$-DNF has an equivalent $k^{2}$-CNF; see [10,
Section 3].

#### Nondeterministic protocols and rectangle covers.

Next we recall standard notions from two-party communication complexity; see
[18, 19] for textbooks. Consider a two-party function $F\colon X\times
Y\to\\{0,1\\}$. A set $A\times B\subseteq X\times Y$ (with $A\subseteq X$ and
$B\subseteq Y$) is called a _rectangle_. Rectangles $R_{1},\ldots,R_{k}$
_cover_ a set $S\subseteq X\times Y$ if $\bigcup_{i}R_{i}=S$. For
$b\in\\{0,1\\}$, the _cover number_ $\mathrm{Cov}_{b}(F)$ is the least number
of rectangles that cover $F^{-1}(b)$. The _nondeterministic (resp., co-
nondeterministic) communication complexity_ of $F$ is defined as
$\mathrm{N}_{1}(F)\coloneqq\log_{2}\mathrm{Cov}_{1}(F)$ (resp.,
$\mathrm{N}_{0}(F):=\log_{2}\mathrm{Cov}_{0}(F)$). Note that
$\mathrm{N}_{0}(F)=\mathrm{N}_{1}(\neg F)$. The nondeterministic communication
complexity can be interpreted as the number of bits that two parties (Alice
and Bob), holding inputs $x\in X$ and $y\in Y$, respectively, need to
communicate in a nondeterministic (i.e., based on guessing and checking)
protocol in order to establish that $F(x,y)=1$; see [18, Chapter 2] for
details.

#### Nondeterministic lifting.

Next we formulate a _lifting theorem_ , which allows us to transfer lower
bounds on the DNF width of an $n$-bit boolean function $f$ to the
nondeterministic communication complexity of a related two-party function $F$.
We first choose a small two-party function
$g\colon\\{0,1\\}^{b}\times\\{0,1\\}^{b}\to\\{0,1\\}$, often called a
_gadget_. Then we compose $f$ with $g$ to construct the function $F\coloneqq
f\circ g^{n}$ that maps $\\{0,1\\}^{bn}\times\\{0,1\\}^{bn}\to\\{0,1\\}$ where
Alice gets as input $x\in\\{0,1\\}^{bn}$, Bob gets as input
$y\in\\{0,1\\}^{bn}$, and their goal is to compute

$F(x,y)\leavevmode\nobreak\ \coloneqq\leavevmode\nobreak\
f(g(x_{1},y_{1}),\ldots,g(x_{n},y_{n}))\qquad\text{where
}x_{i},y_{j}\in\\{0,1\\}^{b}.$

The following is a nondeterministic lifting theorem [12, 10].

######  Theorem 2.2 ([10, Theorem 4]).

For any $n\in\mathbb{N}$ there is a gadget
$g\colon\\{0,1\\}^{b}\times\\{0,1\\}^{b}\to\\{0,1\\}$ with $b=\Theta(\log n)$
such that for any function $f\colon\\{0,1\\}^{n}\to\\{0,1\\}$ we have, for
$F\coloneqq f\circ g^{n}$,

$\mathrm{N}_{0}(F)\leavevmode\nobreak\ =\leavevmode\nobreak\
\Omega(\mathrm{C}_{0}(f)\cdot b)$

(and thus also $\mathrm{N}_{1}(F)=\Omega(\mathrm{C}_{1}(f)\cdot b)$).∎

#### Protocols can simulate automata.

Finally, we need a simple folklore connection between automata and protocols.
To formalise this, we tacitly identify a function
$F\colon\\{0,1\\}^{m_{1}}\times\\{0,1\\}^{m_{2}}\to\\{0,1\\}$ with the
language $F^{-1}(1)\leavevmode\nobreak\ =\leavevmode\nobreak\
\\{xy\in\\{0,1\\}^{m_{1}+m_{2}}\mid F(x,y)=1\\}$.

######  Lemma 2.3.

If a two-party function
$F\colon\\{0,1\\}^{m_{1}}\times\\{0,1\\}^{m_{2}}\to\\{0,1\\}$ admits an NFA
with $s$ states, then $\mathrm{Cov}_{1}(F)\leq s$ (that is,
$\mathrm{N}_{1}(F)\leq\log s$).

######  Proof 2.4.

Let $\mathcal{A}=(Q,\Sigma,\delta,I,F)$ be an NFA with
$L(\mathcal{A})=\\{xy\in\\{0,1\\}^{m_{1}+m_{2}}\mid F(x,y)=1\\}$. We show that
$F^{-1}(1)$ is covered by at most $|Q|$ rectangles. Indeed, $F^{-1}(1)$ equals

$\bigcup_{q\in Q}(\\{x\in\\{0,1\\}^{m_{1}}\mid\exists\,q_{0}\in
I\,.\,q_{0}\xrightarrow{x}q\\})\times(\\{y\in\\{0,1\\}^{m_{2}}\mid\exists\,f\in
F\,.\,q\xrightarrow{y}f\\})\,.$

(Alternatively, in terms of a nondeterministic protocol, the first party,
holding $x\in\\{0,1\\}^{m_{1}}$, produces a run for $x$ from an initial state
to a state $q$ and then sends the name of $q$, which takes $\log_{2}|Q|$ bits,
to the other party. The other party then produces a run for $y$ from $q$ to an
accepting state.)

###  2.2 Proof of Theorem 1.1

For $k\in\mathbb{N}$, let $f\colon\\{0,1\\}^{n}\to\\{0,1\\}$ be the function
from Theorem 2.1. That is, $f$ has an unambiguous $k$-DNF with
$k=n^{\Omega(1)}$ (hence, $\log n=O(\log k)$) and
$\mathrm{C}_{0}(f)=\tilde{\Omega}(k^{2})$. Let
$g\colon\\{0,1\\}^{b}\times\\{0,1\\}^{b}\to\\{0,1\\}$ with $b=\Theta(\log n)$
and $F\coloneqq f\circ
g^{n}\colon\\{0,1\\}^{bn}\times\\{0,1\\}^{bn}\to\\{0,1\\}$ be the two-party
functions from the lifting theorem Theorem 2.2. We will show that Theorem 1.1
holds for the language $F^{-1}(1)$.

First we argue that $F$ has an unambiguous DNF of small width. Indeed, $g$ and
$\neg g$ have unambiguous $2b$-DNFs, which can be extracted from the
deterministic decision tree of $g$. By plugging these unambiguous $2b$-DNFs
for $g$ and $\neg g$ into the unambiguous $k$-DNF for $f$ (and “multiplying
out”), one obtains an unambiguous $2bk$-DNF, say $D$, for $F$.

Over the $2bn$ variables of $F$, there exist at most $(2(2bn)+1)^{2bk}$
different conjunctions of at most $2bk$ literals. So $D$ consists of at most
$n^{O(bk)}$ conjunctions. From $D$ we obtain a UFA $\mathcal{A}$ that
recognizes $F^{-1}(1)\subseteq\\{0,1\\}^{2bn}$, as follows. Each initial state
of $\mathcal{A}$ corresponds to a conjunction in $D$. When reading the input
$x\in\\{0,1\\}^{2bn}$, the UFA checks that the corresponding assignment to the
variables satisfies the conjunction represented by the initial state. This
check requires at most $O(bn)$ states for each initial state. Thus,
$\mathcal{A}$ has at most $n^{O(bk)}=2^{\tilde{O}(k)}\eqqcolon N$ states in
total. (We use $N$ in place of $n$ in the statement of Theorem 1.1.)

On the other hand, by Theorem 2.2, we have
$\mathrm{N}_{0}(F)=\Omega(\mathrm{C}_{0}(f)\cdot b)=\tilde{\Omega}(k^{2})$. So
by Lemma 2.3 any NFA that recognizes $F^{-1}(0)$ has at least
$2^{\tilde{\Omega}(k^{2})}$ states. Any NFA that recognizes
$\\{0,1\\}^{*}\setminus L(\mathcal{A})$ can be transformed into an NFA that
recognizes $F^{-1}(0)=\\{0,1\\}^{2bn}\setminus L(\mathcal{A})$ by taking a
product with a DFA that has $2bn+2$ states. It follows that any NFA that
recognizes $\\{0,1\\}^{*}\setminus L(\mathcal{A})$ has at least
$2^{\tilde{\Omega}(k^{2})}/(2bn+2)=2^{\tilde{\Omega}(k^{2})}=N^{\tilde{\Omega}(\log
N)}$ states. ∎

##  3 UFA Union

In this section, we prove Theorem 1.2. See 1.2

We follow the same high-level approach that we already saw in Section 2.
Namely, we will first show that computing the $\lor$-operation is hard for
unambiguous DNFs and then lift that hardness to unambiguous protocols, which
then implies the same hardness for UFAs. There are, however, two challenges in
carrying out this plan.

  1. 1.

It is an open problem to prove an unambiguous lifting theorem. That is, it is
not known whether the unambiguous communication complexity of $f\circ g^{n}$
is at least $\Omega(\mathrm{UC}_{1}(f))$. To circumvent this issue, we study
instead a _linear relaxation_ of unambiguous DNFs. These objects are called
_conical juntas_ and they do admit a lifting theorem [12, 17].

  2. 2.

There is no existing result showing that the $\lor$-operation is hard for
unambiguous DNFs and/or conical juntas. We show a result of this type. The
proof is by a reduction to the hardness of negating conical juntas, which _is_
a known result [11].

###  3.1 Conical juntas

A nonnegative function $h\colon\\{0,1\\}^{n}\to\mathbb{R}_{\geq 0}$ is a _$d$
-junta_ if $h$ depends on at most $d$ variables. For example, a conjunction of
$d$ literals is a $d$-junta. Moreover, we say
$f\colon\\{0,1\\}^{n}\to\mathbb{R}_{\geq 0}$ a _conical $d$-junta_ if it can
be written as a nonnegative linear combination of $d$-juntas. Equivalently,
$f$ is a conical $d$-junta if it can be written as $f=\sum_{i}w_{i}C_{i}$
where each $C_{i}$ is a width-$d$ conjunction and $w_{i}\in\mathbb{R}_{\geq
0}$ are nonnegative coefficients. For example, if $f$ can be written as an
unambiguous $d$-DNF, $f=C_{1}\lor\cdots\lor C_{m}$, then $f=\sum_{i}C_{i}$ is
a conical $d$-junta with $0/1$ coefficients. The _nonnegative degree_ of $f$,
denoted $\deg^{+}(f)$, is the least $d$ such that $f$ is a conical $d$-junta.
In particular, if $f$ is boolean-valued, then
$\deg^{+}(f)\leq\mathrm{UC}_{1}(f)$.

We also need to work with _approximate_ conical juntas that compute a given
function only to within some point-wise error $\epsilon>0$. This is important
because the available lifting theorems for $\deg^{+}$ incur some error, and
hence we need to prove lower bounds that are robust to this error. Indeed, we
define the _$\epsilon$ -approximate nonnegative degree_ of $f$, denoted
$\deg^{+}_{\epsilon}(f)$, as the least nonnegative degree of a conical junta
$g$ such that

$|f(x)-g(x)|\leavevmode\nobreak\ \leq\leavevmode\nobreak\ \epsilon\qquad\text{
for all }x\in\\{0,1\\}^{n}.$

An awkward aspect of working with approximate conical juntas is that the error
parameter $\epsilon$ is not well behaved. For $0<\epsilon<\delta<1/2$ we of
course have $\deg^{+}_{\delta}(f)\leq\deg^{+}_{\epsilon}(f)$ but it is not a
priori clear whether the converse inequality holds with a modest loss in the
degree. In fact, in Section 5, we will end up showing that there can be a
polynomial gap between the nonnegative degrees corresponding to two different
error parameters—and this is related to our bonus result discussed in the
introduction. As a consequence, our theorems in this section have to track the
error parameters with some care.

#### Linear programming formulation.

Approximate nonnegative degree can be captured using an LP. Write
$\mathcal{C}_{d}^{n}$ for the set of all conjunctions of width at most $d$
over $n$ variables. In the Primal programme below, we have a variable
$w_{C}\in\mathbb{R}$ for every $C\in\mathcal{C}_{d}^{n}$. In the associated
Dual programme, we have a variable $\Phi(x)\in\mathbb{R}$ for each
$x\in\\{0,1\\}^{n}$.  $\begin{array}[]{rll}\min&\epsilon\\\ \textsl{subject
to}&\sum_{C}|w_{C}C(x)-f(x)|\leavevmode\nobreak\ \leq\leavevmode\nobreak\
\epsilon,\quad\mbox{}&\forall x\in\\{0,1\\}^{n}\\\ &w_{C}\leavevmode\nobreak\
\geq\leavevmode\nobreak\ 0,&\forall C\in\mathcal{C}_{d}^{n}\end{array}$
(Primal) $\begin{array}[]{rll}\max&\langle\Phi,f\rangle\leavevmode\nobreak\
\coloneqq\leavevmode\nobreak\ \sum_{x}\Phi(x)f(x)\\\ \textsl{subject
to}&\|\Phi\|\leavevmode\nobreak\ \coloneqq\leavevmode\nobreak\
\sum_{x}|\Phi(x)|\leavevmode\nobreak\ \leq\leavevmode\nobreak\
1\qquad\mbox{}\\\ &\langle\Phi,C\rangle\leavevmode\nobreak\
\leq\leavevmode\nobreak\ 0,&\forall C\in\mathcal{C}_{d}^{n}\end{array}$ (Dual)

We have that $\deg^{+}_{\delta}(f)\leq d$ iff the optimal value of Primal is
at most $\delta$. Alternatively, by strong LP duality, we have
$\deg^{+}_{\delta}(f)>d$ iff there exists a feasible solution $\Phi$ to Dual
such that $\langle\Phi,f\rangle>\delta$. It is typical to think of such
feasible $\Phi\colon\\{0,1\\}^{n}\to\mathbb{R}$ as a _dual certificate_ that
witnesses a lower bound on approximate nonnegative degree.

###  3.2 Hardness of $\lor$

The goal of this subsection is to prove Theorem 3.1 below, which states that
the $\lor$-operation is hard for unambiguous DNFs and even approximate conical
juntas. Given an $n$-bit boolean function $f$ we define a $2n$-bit function by
$f^{\vee}(xy)\coloneqq f(x)\lor f(y)$ where $x,y\in\\{0,1\\}^{n}$.

######  Theorem 3.1 (Hardness of $\lor$).

For every $m\in\mathbb{N}$, there exists a boolean function
$f\colon\\{0,1\\}^{n}\to\\{0,1\\}$ with $n\leq\mathrm{poly}(m)$ such that
$\mathrm{UC}_{1}(f)\leq m$ and $\deg^{+}_{1.5\times
10^{-5}}(f^{\lor})\geq\tilde{\Omega}(m^{2})$.

We show Theorem 3.1 by combining two lemmas, Lemmas 3.2 and 3.3, below. The
first lemma, proved in [11], states that unambiguous DNFs are hard to negate,
even by approximate conical juntas. The second lemma, which remains for us to
prove, states that, for conical juntas, computing $f^{\lor}$ is at least as
hard as computing the negation $\neg f$. Hence Theorem 3.1 follows immediately
by combining these lemmas.

######  Lemma 3.2 (Hardness of $\neg$ [11, Lemma 8]).

For every $m\in\mathbb{N}$, there exists a boolean function
$f\colon\\{0,1\\}^{n}\to\\{0,1\\}$ with $n\leq\mathrm{poly}(m)$ such that
$\mathrm{UC}_{1}(f)\leq m$ and $\deg^{+}_{0.05}(\neg
f)\geq\tilde{\Omega}(m^{2})$. ∎

######  Lemma 3.3 ($\lor$ harder than $\neg$).

For every $\delta>0$ there exists an $\epsilon=\epsilon(\delta)>0$ such that
for every boolean function $f$, we have
$\deg^{+}_{\epsilon}(f^{\vee})\geq\Omega(\deg^{+}_{\delta}(\neg f))$.
Moreover,
$\epsilon\coloneqq\big{(}\frac{\ln(1+\delta)}{\lceil\log_{3/4}\delta\rceil}\big{)}^{2}$.

It remains to prove Lemma 3.3. We do it in two steps. In 1 we show that the
approximate nonnegative degree of $f^{\vee}$ is at least that of $2-f$ by
exhibiting a dual certificate. Then in 2 we show that the approximate
nonnegative degree of $2-f=1+\neg f$ is at least that of $\neg f$ via a
powering trick. The error parameter $\epsilon$ will degrade in both of these
steps. (We will later see that this degradation is, in fact, unavoidable; see
Section 5.)

######  Claim 1.

We have $\deg^{+}_{\epsilon^{2}}(f^{\vee})\geq\deg^{+}_{\epsilon}(2-f)$ for
any boolean-valued $f$ and error $\epsilon$.

######  Proof 3.4.

Let $d\coloneqq\deg^{+}_{\epsilon}(2-f)$ and let
$\Psi\colon\\{0,1\\}^{n}\to\\{0,1\\}$ be a dual certificate witnessing this.
That is, $\left<\Phi,2-f\right>>\epsilon$, $\|\Phi\|\leq 1$, and
$\left<\Phi,C\right>\leq 0$ for all $C\in\mathcal{C}_{d-1}^{n}$. To construct
a dual certificate $\Psi^{\lor}\colon\\{0,1\\}^{2n}\to\\{0,1\\}$ witnessing
$\deg^{+}_{\epsilon^{2}}(f^{\vee})\geq d$, we consider the negated tensor
product (which was found by an educated guess)

$\Phi^{\lor}(x,y)\leavevmode\nobreak\ \coloneqq\leavevmode\nobreak\
-\Phi(x)\Phi(y).$

It remains to check that this is feasible for the dual programme and also that
$\left<\Phi^{\lor},f^{\vee}\right>>\epsilon^{2}$.

  1. 1.

$\left\|\Phi^{\lor}\right\|=\sum_{x,y}|\Phi^{\lor}(x,y)|=\sum_{x,y}|\Phi(x)\Phi(y)|=\sum_{x,y}|\Phi(x)|\cdot|\Phi(y)|=\left\|\Phi\right\|^{2}\leq
1$.

  2. 2.

For any conjunction $C\in\mathcal{C}_{d-1}^{2n}$, we write
$C(x,y)=C_{1}(x)C_{2}(y)$ where $C_{1},C_{2}\in\mathcal{C}_{d-1}^{n}$. Now

$\displaystyle\textstyle\left<\Phi^{\lor},C\right>\leavevmode\nobreak\ $
$\displaystyle\textstyle=\leavevmode\nobreak\
\sum_{x,y}\Phi^{\lor}(x,y)C(x,y)$
$\displaystyle\textstyle=\leavevmode\nobreak\ \sum_{x,y}-\Phi(x)\Phi(y)\cdot
C_{1}(x)C_{2}(y)$ $\displaystyle\textstyle=\leavevmode\nobreak\
-\big{[}\sum_{x}\Phi(x)C_{1}(x)\big{]}\big{[}\sum_{y}\Phi(y)C_{2}(y)\big{]}$
$\displaystyle\textstyle=\leavevmode\nobreak\
-\left<\Phi,C_{1}\right>\left<\Phi,C_{2}\right>$
$\displaystyle\textstyle\leq\leavevmode\nobreak\ 0.$

  3. 3.

Observe that $\left<\Phi,-f\right>\geq\left<\Phi,2-f\right>$ since
$1\in\mathcal{C}_{d-1}^{n}$ for the constant-1 function. Thus

$\displaystyle\left<\Phi^{\lor},f^{\vee}\right>$
$\displaystyle\textstyle\leavevmode\nobreak\ =\leavevmode\nobreak\
\sum_{x,y}\Phi^{\lor}(x,y)(f(x)+f(y)-f(x)f(y))$
$\displaystyle\textstyle\leavevmode\nobreak\ =\leavevmode\nobreak\
\sum_{x,y}-\Phi(x)\Phi(y)(f(x)+f(y)-f(x)f(y))$
$\displaystyle\textstyle\leavevmode\nobreak\ =\leavevmode\nobreak\
\sum_{x,y}-\Phi(x)\Phi(y)(2f(x)-f(x)f(y))$
$\displaystyle\textstyle\leavevmode\nobreak\ =\leavevmode\nobreak\
\sum_{x}-\Phi(x)f(x)\cdot\big{[}\sum_{y}\Phi(y)(2-f(y))\big{]}$
$\displaystyle\textstyle\leavevmode\nobreak\ =\leavevmode\nobreak\
\left<\Phi,-f\right>\cdot\left<\Phi,2-f\right>$
$\displaystyle\textstyle\leavevmode\nobreak\ \geq\leavevmode\nobreak\
\left<\Phi,2-f\right>\cdot\left<\Phi,2-f\right>$ (above observation)
$\displaystyle\textstyle\leavevmode\nobreak\ >\leavevmode\nobreak\
\epsilon^{2}.$

######  Claim 2.

For any $\delta>0$ define
$\epsilon\coloneqq\frac{\ln(1+\delta)}{\lceil\log_{3/4}\delta\rceil}>0$. Then
for any boolean-valued function $f$ we have
$\deg^{+}_{\epsilon}(1+f)\geq\Omega(\deg^{+}_{\delta}(f))$.

######  Proof 3.5.

We may assume $\delta<1/2$ (and hence $\epsilon<1/4$) as otherwise the claim
is trivial. Suppose $\deg^{+}_{\epsilon}(1+f)=d$ is witnessed by a conical
$d$-junta $g$ that $\epsilon$-approximates $1+f$. Define
$g^{\prime}\coloneqq((g+\epsilon)/2)^{k}$ where the exponent is
$k\coloneqq\lceil\log_{3/4}\delta\rceil$. By multiplying out the terms in this
definition, we see that $g^{\prime}$ has nonnegative degree $kd=O(d)$. We
claim that $g^{\prime}$ is a $\delta$-approximation of $f$. Indeed, if
$f(x)=0$, then $g^{\prime}(x)\leq(1/2+\epsilon)^{k}\leq(3/4)^{k}\leq\delta$.
If $f(x)=1$, then $1\leq(g(x)+\epsilon)/2\leq 1+\epsilon$, and thus $1\leq
g^{\prime}(x)\leq(1+\epsilon)^{k}\leq\exp(\epsilon k)\leq 1+\delta$.

######  Proof 3.6 (Proof of Lemma 3.3).

Using 1 and 2 (but with $\neg f$ in place of $f$), we have, for any $\delta>0$
and $\epsilon\coloneqq\frac{\ln(1+\delta)}{\lceil\log_{3/4}\delta\rceil}$:

$\deg^{+}_{\epsilon^{2}}(f^{\vee})\leavevmode\nobreak\
\geq\leavevmode\nobreak\ \deg^{+}_{\epsilon}(2-f)\leavevmode\nobreak\
=\leavevmode\nobreak\ \deg^{+}_{\epsilon}(1+\neg f)\leavevmode\nobreak\
\geq\leavevmode\nobreak\ \Omega(\deg^{+}_{\delta}(\neg f)).$

###  3.3 Unambiguous protocols and nonnegative rank

Our goal will be to _lift_ the hardness of the $\lor$-operation (Theorem 3.1)
to communication complexity. In this subsection, we recall the concepts that
are needed for this goal, namely, unambiguous protocols, (approximate)
nonnegative rank, and a lifting theorem from nonnegative degree to nonnegative
rank [12, 17].

#### Unambiguous protocols.

Recall from Section 2.1 the notions of nondeterministic protocols and
rectangle covers. For a two-party function $F\colon X\times Y\to\\{0,1\\}$,
the _partition number_ $\mathrm{Par}_{1}(F)$ is the least number of _pairwise
disjoint_ rectangles that cover $F^{-1}(1)$. Note that
$\mathrm{Cov}_{1}(F)\leq\mathrm{Par}_{1}(F)$. The _unambiguous communication
complexity_ of $F$ is defined as
$\mathrm{U}_{1}(F)\coloneqq\log_{2}\mathrm{Par}_{1}(F)$. Note that
$\mathrm{N}_{1}(F)\leq\mathrm{U}_{1}(F)$. Unambiguous communication complexity
can be interpreted as the least communication cost of a nondeterministic
protocol that has at most one accepting computation on every input. We also
have the following folklore lemma, proved the same way as Lemma 2.3, which
states that UFAs are simulated by unambiguous protocols.

######  Lemma 3.7.

If a two-party function
$F\colon\\{0,1\\}^{m_{1}}\times\\{0,1\\}^{m_{2}}\to\\{0,1\\}$ admits an UFA
with $s$ states, then $\mathrm{Par}_{1}(F)\leq s$ (that is,
$\mathrm{U}_{1}(F)\leq\log s$). ∎

#### Nonnegative rank.

We often think of a two-party function $F\colon X\times Y\to\\{0,1\\}$ as a
boolean matrix $F\in\\{0,1\\}^{X\times Y}$, sometimes called the
_communication matrix_ of $F$. For a nonnegative matrix $M\in\mathbb{R}_{\geq
0}^{X\times Y}$ we define its _nonnegative rank_ , denoted
$\mathrm{rk}^{+}(M)$, as the least $r$ such that $M$ can be written as a sum
of $r$ nonnegative rank-1 matrices, i.e.,
$M=\sum_{i=1}^{r}u_{i}v_{i}^{\textrm{T}}$, where $u_{i}\in\mathbb{R}^{X}_{\geq
0}$ and $v_{i}\in\mathbb{R}^{Y}_{\geq 0}$ are nonnegative vectors. Note that
for a boolean matrix $F$,

$\mathrm{Par}_{1}(F)\leavevmode\nobreak\ \geq\leavevmode\nobreak\
\mathrm{rk}^{+}(F)\qquad\text{and
thus}\qquad\mathrm{U}_{1}(F)\leavevmode\nobreak\ \geq\leavevmode\nobreak\
\log\mathrm{rk}^{+}(F).$ (2)

Indeed, if $F^{-1}(1)$ can be partitioned into $r$ rectangles,
$F^{-1}(1)=R_{1}\sqcup\cdots\sqcup R_{r}$, then $F$ can be written as a sum of
$r$ nonnegative rank-1 matrices, $F=M_{1}+\cdots+M_{r}$, where $M_{i}$ is $1$
on the rectangle $R_{i}$ and $0$ elsewhere. As with nonnegative degree, we
define an approximate version of nonnegative rank. The _$\epsilon$
-approximate nonnegative rank_ of $M$, denoted
$\mathrm{rk}_{\epsilon}^{+}(M)$, is defined as the least $\mathrm{rk}^{+}(N)$
over all nonnegative matrices $N$ that $\epsilon$-approximate $M$, i.e.,

$|M_{ij}-N_{ij}|\leavevmode\nobreak\ \leq\leavevmode\nobreak\
\epsilon\qquad\text{for all }i,j.$

#### Nonnegative lifting.

Finally, we formulate a theorem that lifts lower bounds on the nonnegative
degree of an $n$-bit boolean function $f$ to the nonnegative rank of the
composed function $F=f\circ g^{n}$ (which was defined in Section 2.1).

######  Theorem 3.8 ([12, 17]).

Fix constants $\delta>\epsilon>0$. For any $n\in\mathbb{N}$ there is a gadget
$g\colon\\{0,1\\}^{b}\times\\{0,1\\}^{b}\to\\{0,1\\}$ with $b=\Theta(\log n)$
such that for any $f\colon\\{0,1\\}^{n}\to\\{0,1\\}$ we have

$\log\mathrm{rk}_{\epsilon}^{+}(f\circ g^{n})\leavevmode\nobreak\
\geq\leavevmode\nobreak\ \Omega(\deg^{+}_{\delta}(f)\cdot b).$

###  3.4 Proof of Theorem 1.2 (and also Theorem 1.4)

We start with the function $f\colon\\{0,1\\}^{n}\to\\{0,1\\}$ given by Theorem
3.1 such that for $m=\mathrm{poly}(n)$,

$\displaystyle\mathrm{UC}_{1}(f)$ $\displaystyle\leavevmode\nobreak\
\leq\leavevmode\nobreak\ m,$ (2) $\displaystyle\deg^{+}_{1.5\times
10^{-5}}(f^{\lor})$ $\displaystyle\leavevmode\nobreak\
\geq\leavevmode\nobreak\ \tilde{\Omega}(m^{2}).$ (3)

We then use the gadget $g$ on $b=\Theta(\log n)$ bits from the lifting theorem
Theorem 3.8 to construct $F\coloneqq f\circ g^{n}$. By the same argument as in
Section 2.2 we see that the resulting
$F\colon\\{0,1\\}^{nb}\times\\{0,1\\}^{nb}\to\\{0,1\\}$ enjoys the following
upper bounds, derived from 2.

  * •

$F$ admits an unambiguous DNF of width $2bm=\tilde{O}(m)$.

  * •

$F$ admits an UFA of size $2^{\tilde{O}(m)}$.

  * •

$F$ admits an unambiguous protocol of cost
$\mathrm{U}_{1}(F)\leq\tilde{O}(m)$.

On the other hand, we note that $F^{\lor}=(f\circ g^{n})^{\lor}=f^{\lor}\circ
g^{n}$. Hence, we may combine 2, Theorem 3.8, and 3 to conclude that

$\mathrm{U}_{1}(F^{\lor})\leavevmode\nobreak\ \geq\leavevmode\nobreak\
\log\mathrm{rk}^{+}_{10^{-5}}(F^{\lor})\leavevmode\nobreak\
\geq\leavevmode\nobreak\ \Omega(\deg^{+}_{1.5\times
10^{-5}}(f^{\lor}))\leavevmode\nobreak\ \geq\leavevmode\nobreak\
\tilde{\Omega}(m^{2}).$ (4)

This finishes the proof of Theorem 1.4. We proceed with the proof of Theorem
1.2. To this end, we define two languages

$\displaystyle L_{1}$ $\displaystyle\leavevmode\nobreak\
\coloneqq\leavevmode\nobreak\
\\{xx^{\prime}yy^{\prime}:x,x^{\prime},y,y^{\prime}\in\\{0,1\\}^{bn}\text{ and
}F(x,y)=1\\},$ $\displaystyle L_{2}$ $\displaystyle\leavevmode\nobreak\
\coloneqq\leavevmode\nobreak\
\\{xx^{\prime}yy^{\prime}:x,x^{\prime},y,y^{\prime}\in\\{0,1\\}^{bn}\text{ and
}F(x^{\prime},y^{\prime})=1\\}.$

Both $L_{1}$ and $L_{2}$ admit UFAs of size $\mathrm{poly}(n)\cdot
2^{\tilde{O}(m)}=2^{\tilde{O}(m)}\eqqcolon N$. By contrast, we have $L_{1}\cup
L_{2}=(F^{\lor})^{-1}(1)$, and this union language requires UFAs of size
$2^{\tilde{\Omega}(m^{2})}=N^{\tilde{\Omega}(\log N)}$ by 4 and Lemma 3.7.
This concludes the proof of Theorem 1.2. ∎

##  4 UFA Separation

In this section, we prove Theorem 1.3. See 1.3

Loosely speaking, in our construction, we define NFAs
$\mathcal{A}_{1},\mathcal{A}_{2}$ that recognize _(sparse) set disjointness_
and its complement. For $n\in\mathbb{N}$ and $k\leq n$ we define

$\displaystyle\textsc{Disj}^{n}_{k}\ $ $\displaystyle\coloneqq\ \\{(S,T)\mid
S\subseteq[n],\ T\subseteq[n],\ |S|=|T|=k,\ S\cap T=\emptyset\\}\,.$

Define also $\langle\textsc{Disj}^{n}_{k}\rangle\coloneqq\\{\langle
S\rangle\langle T\rangle\mid(S,T)\in\textsc{Disj}^{n}_{k}\\}$ where $\langle
S\rangle\in\\{0,1\\}^{n}$ is such that the $i$th letter of $\langle S\rangle$
is $1$ if and only if $i\in S$, and similarly for $\langle T\rangle$. Note
that $\langle S\rangle,\langle T\rangle$ each contain $k$ times the letter
$1$. To prove Theorem 1.3 it suffices to prove the following lemma.

######  Lemma 4.1.

For any $n\in\mathbb{N}$ let $k\coloneqq\lceil\log_{2}n\rceil$. There are NFAs
$\mathcal{A}_{1},\mathcal{A}_{2}$ with $n^{O(1)}$ states such that
$L(\mathcal{A}_{1})=\langle\textsc{Disj}^{n}_{k}\rangle$ and
$L(\mathcal{A}_{2})=\\{0,1\\}^{*}\setminus\langle\textsc{Disj}^{n}_{k}\rangle$.
Any UFA that recognizes $\langle\textsc{Disj}^{n}_{k}\rangle$ has at least
$n^{\Omega(\log n)}$ states.

In the rest of the section we prove Lemma 4.1 by following Razborov’s analysis
of sparse set disjointness [21]. In particular, we will give a self-contained
proof of the existence of polynomial-sized NFAs for
$\langle\textsc{Disj}^{n}_{k}\rangle$ and its complement, but the main
argument also comes from communication complexity.

###  4.1 Proof of Lemma 4.1

First we prove the statement on UFAs. Write
$\binom{[n]}{k}\coloneqq\\{S\subseteq[n]\mid|S|=k\\}$. Let
$F\colon\binom{[n]}{k}\times\binom{[n]}{k}\to\\{0,1\\}$ be the two-party
function with $F(S,T)=1$ if and only if $(S,T)\in\textsc{Disj}^{n}_{k}$. It is
shown, e.g., in [18, Example 2.12] that the communication matrix of $F$ has
full rank, $\mathrm{rk}(F)=\binom{n}{k}$. Let
$F^{\prime}\colon\\{0,1\\}^{n}\times\\{0,1\\}^{n}\to\\{0,1\\}$ be such that
$F^{\prime}(x,y)=1$ if and only if $xy\in\langle\textsc{Disj}^{n}_{k}\rangle$.
Then $F$ is a principal submatrix of $F^{\prime}$, so
$\binom{n}{k}\leq\mathrm{rk}(F^{\prime})$. Using 2 and 3.7 it follows that any
UFA, say $\mathcal{A}$, that recognizes $\langle\textsc{Disj}^{n}_{k}\rangle$
has at least $\binom{n}{k}\geq(\frac{n}{k})^{k}$ states. With
$k\coloneqq\lceil\log_{2}n\rceil$, it follows that $\mathcal{A}$ has
$n^{\Omega(\log n)}$ states.

It is easy to see that there is an NFA, $\mathcal{A}_{2}$, with $n^{O(1)}$
states and
$L(\mathcal{A}_{2})=\\{0,1\\}^{*}\setminus\langle\textsc{Disj}^{n}_{k}\rangle$.
Indeed, we can assume that the input is of the form $\langle S\rangle\langle
T\rangle$; otherwise $\mathcal{A}_{2}$ accepts. NFA $\mathcal{A}_{2}$ guesses
$i\in[n]$ such that $i\in S\cap T$ and then checks it.

Finally, we show that there is an NFA, $\mathcal{A}_{1}$, with $n^{O(1)}$
states and $L(\mathcal{A}_{1})=\langle\textsc{Disj}^{n}_{k}\rangle$. We can
assume that the input is of the form $\langle S\rangle\langle T\rangle$;
otherwise $\mathcal{A}_{1}$ rejects. NFA $\mathcal{A}_{1}$ “hard-codes”
polynomially many sets $Z_{1},\ldots,Z_{\ell}\subseteq[n]$. It guesses
$i\in[\ell]$ such that $S\subseteq Z_{i}$ and $Z_{i}\cap T=\emptyset$ and then
checks it. It remains to show that there exist $\ell=n^{O(1)}$ sets
$Z_{1},\ldots,Z_{\ell}\subseteq[n]$ such that for any
$(S,T)\in\textsc{Disj}^{n}_{k}$ there is $i\in[\ell]$ with $S\subseteq Z_{i}$
and $Z_{i}\cap T=\emptyset$. The argument uses the probabilistic method and is
due to [21]; see also [18, Example 2.12]. We reproduce it here due to its
elegance and brevity.

Fix $(S,T)\in\textsc{Disj}^{n}_{k}$. Say that a set $Z\subseteq[n]$
_separates_ $(S,T)$ if $S\subseteq Z$ and $Z\cap T=\emptyset$. A random set
$Z\subseteq[n]$ (each $i$ is in $Z$ with probability $1/2$) separates $(S,T)$
with probability $2^{-2k}$. Thus, choosing
$\ell\coloneqq\big{\lceil}2^{2k}\ln\binom{n}{k}^{2}\big{\rceil}=n^{O(1)}$
random sets $Z\subseteq[n]$ independently, the probability that none of them
separates $(S,T)$ is

$\textstyle(1-2^{-2k})^{\ell}\leavevmode\nobreak\ <\leavevmode\nobreak\
e^{-2^{-2k}\ell}\leavevmode\nobreak\ \leq\leavevmode\nobreak\
\binom{n}{k}^{-2}\,.$

By the union bound, since $|\textsc{Disj}^{n}_{k}|<\binom{n}{k}^{2}$, the
probability that there exists $(S,T)\in\textsc{Disj}^{n}_{k}$ such that none
of $\ell$ random sets separates $(S,T)$ is less than $1$. Equivalently, the
probability that for all $(S,T)\in\textsc{Disj}^{n}_{k}$ at least one of
$\ell$ random sets separates $(S,T)$ is positive. It follows that there are
$Z_{1},\ldots,Z_{\ell}\subseteq[n]$ such that each
$(S,T)\in\textsc{Disj}^{n}_{k}$ is separated by some $Z_{i}$. ∎

##  5 Bonus result: Approximate nonnegative rank

In this section, we prove Theorem 1.5.

See 1.5

We first illustrate the idea in the context of nonnegative degree. In contrast
to Theorem 3.1 (which states that $\lor$ is hard to approximate to within tiny
error), we show that the $\lor$-operation is, in fact, easy to approximate
when we allow large enough error.

######  Claim 3.

For any boolean-valued $f$, we have $\deg^{+}_{1/4}(f^{\vee})\leq\deg^{+}(f)$.

######  Proof 5.1.

Let $g\colon\\{0,1\\}^{2n}\rightarrow\mathbb{R}_{\geq 0}$ be given by
$g(x,y)\coloneqq(f(x)+f(y))/2+1/4$. Then

$g(x,y)\leavevmode\nobreak\ =\leavevmode\nobreak\ \begin{cases}1/4&\text{if
}f(x)=f(y)=0,\\\ 5/4&\text{if }f(x)=f(y)=1,\\\
3/4&\text{otherwise}.\end{cases}$

Thus $g$ is a $1/4$-approximation to $f^{\vee}$. Note also that
$\deg^{+}(g)\leq\deg^{+}(f)$, as desired.

We can now repeat the same idea for nonnegative rank. In Section 3.4 we
constructed a boolean matrix (two-party function) $F$ such that
$\log\mathrm{rk}^{+}(F)\leq\mathrm{U}_{1}(F)\leq m$ and
$\log\mathrm{rk}_{10^{-5}}^{+}(F^{\lor})\geq\tilde{\Omega}(m^{2})$. We claim
that $\log\mathrm{rk}_{1/4}^{+}(F^{\lor})\leq O(m)$, which would finish the
proof of Theorem 1.5. Indeed, analogously to 3, we can define a nonnegative
matrix by $G(xx,yy^{\prime})\coloneqq(F(x,y)+F(x^{\prime},y^{\prime}))/2+1/4$.
This is a $1/4$-approximation to $F^{\lor}$ and we have
$\mathrm{rk}^{+}(G)\leq 2\cdot\mathrm{rk}^{+}(F)+1\leq 2^{m+1}+1$, as claimed.

## References

  * [1] Noga Alon.  Problems and results in extremal combinatorics–I.  Discrete Mathematics, 273(1–3):31–53, 2003.  %For␣bibliographydoi:10.1016/S0012-365X(03)00227-9.
  * [2] Kaspars Balodis, Shalev Ben-David, Mika Göös, Siddhartha Jain, and Robin Kothari.  Unambiguous DNFs and Alon-Saks-Seymour.  In 62nd IEEE Annual Symposium on Foundations of Computer Science (FOCS), 2021.  To appear. Available at https://arxiv.org/abs/2102.08348.
  * [3] Jean-Camille Birget.  Partial orders on words, minimal elements of regular languages, and state complexity.  Theoretical Computer Science, 119(2):267–291, 1993.  %For␣bibliographydoi:10.1016/0304-3975(93)90160-U.
  * [4] Mikołaj Bojańczyk and Wojciech Czerwiński.  An Automata Toolbox.  2018\.  Available at https://www.mimuw.edu.pl/~bojan/paper/automata-toolbox-book.
  * [5] Thomas Colcombet.  Unambiguity in automata theory.  In 17th International Workshop on Descriptional Complexity of Formal Systems (DCFS), volume 9118 of Lecture Notes in Computer Science, pages 3–18. Springer, 2015.  %For␣bibliographydoi:10.1007/978-3-319-19225-3\\_1.
  * [6] Thomas Colcombet, Karin Quaas, and Michał Skrzypczak.  Unambiguity in automata theory (Dagstuhl seminar 21452).  Dagstuhl Reports, 2021.  To appear.
  * [7] Wojciech Czerwiński, Laure Daviaud, Nathanaël Fijalkow, Marcin Jurdziński, Ranko Lazić, and Pawel Parys.  Universal trees grow inside separating automata: Quasi-polynomial lower bounds for parity games.  In Proceedings of the 2019 Annual ACM-SIAM Symposium on Discrete Algorithms (SODA), pages 2333–2349, 2019.  %For␣bibliographydoi:10.1137/1.9781611975482.142.
  * [8] Wojciech Czerwiński and Sławomir Lasota.  Regular separability of one counter automata.  Logical Methods in Computer Science, 15(2), 2019.  %For␣bibliographydoi:10.23638/LMCS-15(2:20)2019.
  * [9] Yuan Gao, Nelma Moreira, Rogério Reis, and Sheng Yu.  A survey on operational state complexity.  Journal of Automata, Languages and Combinatorics, 21(4):251–310, 2016.  %For␣bibliographydoi:10.25596/jalc-2016-251.
  * [10] Mika Göös.  Lower bounds for clique vs. independent set.  In IEEE 56th Annual Symposium on Foundations of Computer Science (FOCS), pages 1066–1076. IEEE Computer Society, 2015.  %For␣bibliography%****␣ufa_main.tex␣Line␣200␣****doi:10.1109/FOCS.2015.69.
  * [11] Mika Göös, T.S. Jayram, Toniann Pitassi, and Thomas Watson.  Randomized communication versus partition number.  ACM Transactions on Computation Theory (TOCT), 10(1):1–20, 2018\.  %For␣bibliographydoi:10.1145/3170711.
  * [12] Mika Göös, Shachar Lovett, Raghu Meka, Thomas Watson, and David Zuckerman.  Rectangles are nonnegative juntas.  SIAM Journal on Computing, 45(5):1835–1869, 2016.  %For␣bibliographydoi:10.1137/15M103145X.
  * [13] Emil Indzhev and Stefan Kiefer.  On complementing unambiguous automata and graphs with many cliques and cocliques.  Technical report, arxiv.org, 2021.  Available at https://arxiv.org/abs/2105.07470.
  * [14] Galina Jirásková.  State complexity of some operations on binary regular languages.  Theoretical Computer Science, 330(2):287–298, 2005.  %For␣bibliographydoi:10.1016/j.tcs.2004.04.011.
  * [15] Jozef Jirásek Jr., Galina Jirásková, and Juraj Šebej.  Operations on unambiguous finite automata.  International Journal of Foundations of Computer Science, 29(5):861–876, 2018.  %For␣bibliographydoi:10.1142/S012905411842008X.
  * [16] Gillat Kol, Shay Moran, Amir Shpilka, and Amir Yehudayoff.  Approximate nonnegative rank is equivalent to the smooth rectangle bound.  Computational Complexity, 28(1):1–25, 2019.  Preliminary version in _ICALP ’14_.  %For␣bibliographydoi:10.1007/s00037-018-0176-4.
  * [17] Pravesh Kothari, Raghu Meka, and Prasad Raghavendra.  Approximating rectangles by juntas and weakly exponential lower bounds for LP relaxations of CSPs.  SIAM Journal on Computing, pages STOC17–305–STOC17–332, May 2021.  Preliminary version in _STOC ’17_.  %For␣bibliographydoi:10.1137/17m1152966.
  * [18] Eyal Kushilevitz and Noam Nisan.  Communication Complexity.  Cambridge University Press, 1997.  %For␣bibliographydoi:10.1017/CBO9780511574948.
  * [19] Anup Rao and Amir Yehudayoff.  Communication Complexity: And Applications.  Cambridge University Press, 2020.  %For␣bibliographydoi:10.1017/9781108671644.
  * [20] Mikhail Raskin.  A superpolynomial lower bound for the size of non-deterministic complement of an unambiguous automaton.  In 45th International Colloquium on Automata, Languages, and Programming (ICALP 2018), volume 107 of Leibniz International Proceedings in Informatics (LIPIcs), pages 138:1–138:11, 2018.  %For␣bibliographydoi:10.4230/LIPIcs.ICALP.2018.138.
  * [21] Alexander Razborov.  Applications of matrix methods to the theory of lower bounds in computational complexity.  Combinatorica, 10(1):81–93, 1990.  %For␣bibliographydoi:10.1007/BF02122698.
  * [22] Wikipedia.  State complexity.  URL: https://en.wikipedia.org/wiki/State_complexity.
  * [23] Mihalis Yannakakis.  Expressing combinatorial optimization problems by linear programs.  Journal of Computer and System Sciences, 43(3):441–466, 1991.  %For␣bibliography%****␣ufa_main.tex␣Line␣300␣****doi:10.1016/0022-0000(91)90024-Y.


# Gluons in the Charmonium(-like) States

Wei Sun1, Ying Chen1,2, Peng Sun3, Yi-Bo Yang4,5,6 ($\chi$QCD Collaboration)
1Institute of High Energy Physics, Chinese Academy of Sciences, Beijing
100049, China
2School of Physics, University of Chinese Academy of Sciences, Beijing 100049,
China
3Nanjing Normal University, Nanjing, Jiangsu, 210023, China
4CAS Key Laboratory of Theoretical Physics, Institute of Theoretical Physics,
Chinese Academy of Sciences, Beijing 100190, China
5School of Fundamental Physics and Mathematical Sciences, Hangzhou Institute
for Advanced Study, UCAS, Hangzhou 310024, China
6International Centre for Theoretical Physics Asia-Pacific, Beijing/Hangzhou,
China

###### Abstract

The mass components of charmonium(-like) states are investigated through the
decomposition of QCD energy-momentum tensor (EMT) on lattice. The quark mass
contribution $\langle H_{m}\rangle$ and the momentum fraction $\langle
x\rangle$ of valence charm quark and antiquark are calculated for conventional
$1S,1P,1D$ charmonia and the exotic $1^{-+}$ charmonium-like state, based on
the $N_{f}=2+1$ gauge configurations generated by the RBC/UKQCD collaboration.
It is found that $\langle H_{m}\rangle$ is around 2.0 to 2.2 GeV for these
states, which implies that the mass splittings among these states come almost
all from the contribution of QCD anomaly and ultimately the gluon
contribution. The $\langle x\rangle$ of the $1^{-+}$ state is only around
0.55, while that in conventional charmonia is around 0.7 to 0.8. This
difference manifests that the proportion of light quarks and gluons in the
$1^{-+}$ charmonium-like state is significantly larger than conventional
states.

Introduction: In the view of non-relativistic quark model, charmonia are bound
states of a charm quark-antiquark pair, whose spectrum can be calculated by
solving the Schrödinger equation with phenomenological confining potential
parameters and the constituent charm quark mass. Since gluons are fundamental
degrees of freedom of quantum chromodynamics (QCD) as well as quarks, it is
possible for them to be important ingredients of hadrons Shifman  _et al._
(1978); Ji (1995). For example, the deep inelastic lepton-nucleon scattering
experiments find that the momentum fraction of gluons in a nucleon is as large
as 50%. This is consistent with a lattice calculation based on the
decomposition of the QCD energy-momentum tensor (EMT), which also predicts
that gluons contribute approximately 50% of the nucleon rest frame energy Yang
_et al._ (2018). With regard to these observations, it is necessary and
important to investigate the role of gluons in charmonium(-like) states. On
the other hand, QCD expects the existence of hybrid mesons made up of
$q\bar{q}$ and excitation of gluon, among them the $J^{PC}=1^{-+}$ state is
one of the most interesting states, since this quantum number is prohibited by
a $q\bar{q}$ system in the constituent quark model. Through the study of it,
we can know whether the gluonic contributions are comparable or not between
the conventional charmonia and exotic charmonium-like states. In this letter,
we will focus on the mass components of the $1S(\eta_{c},J/\psi)$,
$1P(h_{c},\chi_{c0,1,2})$, $1D(\eta_{c2})$ charmonia, as well as the $1^{-+}$
charmonium-like state.

One can start from the symmetrized QCD EMT in the Euclidean spacetime,

$T_{\mu\nu}=\frac{1}{4}\sum\limits_{q}\bar{\psi}_{q}\gamma_{\\{\mu}\overleftrightarrow{D}_{\nu\\}}\psi_{q}+F_{\mu\alpha}F_{\nu\alpha}-\frac{1}{4}\delta_{\mu\nu}F^{2},$
(1)

where $\psi_{q}$ is the quark field of flavor $q$, $F_{\mu\nu}$ is the gluon
field strength tensor,
$\overleftrightarrow{D}_{\mu}\equiv\overrightarrow{D}_{\mu}-\overleftarrow{D}_{\mu}$
is the difference between the forward and backward covariant derivatives
$D_{\mu}=\partial_{\mu}-igA_{\mu}$. Thus the mass of a hadron is defined in
terms of the matrix element of $T_{44}$, which can be decomposed as in Ref. Ji
(1995) (An alternative decomposition scheme was discussed in Ref. Lorcé
(2018)),

$M\equiv-\int d^{3}x\langle T_{44}\rangle=\langle H_{m}\rangle+\langle
H_{E}\rangle(\mu)+\langle H_{g}\rangle(\mu)+\frac{1}{4}\langle H_{a}\rangle,$
(2)

where $H_{m}$, $H_{E}$, $H_{g}$ and $H_{a}$ denote the parts of the
Hamiltonian contributed by the quark mass, quark energy, glue energy and QCD
anomaly, respectively, whose explicit forms are

$\displaystyle H_{m}$ $\displaystyle=\sum_{q=u,d,s\cdots}\int
d^{3}xm_{q}\bar{\psi}_{q}\psi_{q},$ $\displaystyle H_{E}$
$\displaystyle=\sum_{q=u,d,s\ldots}\int
d^{3}x\bar{\psi}_{q}(\vec{D}\cdot\vec{\gamma})\psi_{q},~{}H_{g}=\int
d^{3}x\frac{1}{2}\left(B^{2}-E^{2}\right),$ $\displaystyle H_{a}$
$\displaystyle=\int
d^{3}x\big{[}\sum_{q=u,d,s\cdots}\gamma_{m}m_{q}\bar{\psi}_{q}\psi_{q}-\frac{\beta(g)}{g}\left(E^{2}+B^{2}\right)\big{]}.$
(3)

Here $\langle\cdots\rangle$ means $\langle h|\ldots|h\rangle/\langle
h|h\rangle$ with $|h\rangle$ being the hadron state in its rest frame.
Considering the relation $M=\langle H_{m}\rangle+\langle H_{a}\rangle$ Shifman
_et al._ (1978), then there are only two independent components in Eq. (2).
Following the strategy proposed in Ref. Yang  _et al._ (2018), we will
calculate the hadron mass $M$, the quark mass contribution $\langle
H_{m}\rangle$, the momentum fraction $\langle x\rangle_{q}$ and obtain the
total quark contribution through the relation,

$\displaystyle\langle H_{q}^{R}\rangle=\langle H_{E}^{R}\rangle+\langle
H_{m}\rangle=\frac{3}{4}\langle x\rangle^{R}_{q}M+\frac{1}{4}\langle
H_{m}\rangle,$ (4)

where superscript $R$ denote a renormalization scheme at a certain energy
scale. Thus the gluon energy $\langle H_{g}^{R}\rangle$ and the QCD trace
anomaly part $\langle H_{a}\rangle$ can be obtained from $M=\langle
H_{m}\rangle+\langle H_{a}\rangle$ and Eq. (2).

Numerical strategy: We perform the calculation using the 2+1 flavor
configurations of domain wall fermion and Iwasaki gauge action Aoki  _et al._
(2011); Mawhinney (2019) provided by RBC/UKQCD collaboration. Two gauge
ensembles are used with the parameters listed in Table 1. The overlap fermion
is adopted for the valence charm quark whose bare quark mass parameters on the
two ensembles are tuned to reproduce the physical $J/\psi$ mass
$M_{J/\psi}=3.097\mathrm{GeV}$. One of the advantages of the implementation of
the overlap fermion Chiu and Zenkin (1999) is the absence of the additive
renormalization in the $\langle H_{m}\rangle$, such that $\langle
H_{m}\rangle$ is automatically free of renormalization. We use the
conventional quark bilinear operators $\bar{c}\Gamma(D)c$ for
$1S(\eta_{c},J/\psi)$, $1P(h_{c},\chi_{c0,1,2}$) and $1D(\eta_{c2})$
charmonium states, where $\Gamma$ stands for the specific combinations of
gamma matrices and $D$ is the lattice covariant derivative operator. For the
$1^{-+}$ charmonium-like state, the operator is chosen to be
$\epsilon_{ijk}\bar{c}\gamma_{j}B_{k}c$ where $B_{k}$ is the chromomagnetic
strength tensor. The details of the lattice interpolation operators and their
quantum numbers can be found in Table 2, where the available experiment
results of masses of conventional charmonia in Ref. Zyla  _et al._ (2020) are
also listed .

Table 1: The parameters of gauge ensembles. The pion mass $m_{\pi}$ corresponds to the $u,d$ sea quark mass parameter, while the bare quark mass parameter $m_{c}a$ on each ensemble is set by the physical $J/\psi$ mass $M_{J/\psi}=3.097\mathrm{GeV}$, and $N_{\text{cfg}}$ is the number of configurations used in the calculation. ensemble | $L^{3}\times T$ |  $a$ (fm) |  $m_{\pi}$ (MeV) | $m_{c}a$ | $N_{\text{cfg}}$
---|---|---|---|---|---
32I | $32^{3}\times 64$ | 0.0828(3) | 300 | 0.493 | 305
48If | $48^{3}\times 96$ | 0.0711(3) | 278 | 0.410 | 205
Table 2:  Meson interpolation operators for different $J^{PC}$ quantum numbers used in this work and the masses collected from PDG Zyla  _et al._ (2020) for $1S,~{}1P$ charmonia, where $D$ is lattice derivative operator and $B$ is the chromomagnetic gluon field from clover discretization of field strength.  meson | $J^{PC}$ | operator | mass(GeV) Zyla  _et al._ (2020)
---|---|---|---
$\eta_{c}({}^{1}S_{0})$ | $0^{-+}$ | $\gamma_{5}$ | 2.984
$J/\psi({}^{3}S_{1})$ | $1^{--}$ | $\gamma_{i}$ | 3.097
$\chi_{c0}({}^{3}P_{0})$ | $0^{++}$ | ${\cal I}$ | 3.415
$\chi_{c1}({}^{3}P_{1})$ | $1^{++}$ | $\gamma_{5}\gamma_{i}$ | 3.511
$h_{c}({}^{1}P_{0})$ | $1^{+-}$ | $\gamma_{4}\gamma_{5}\gamma_{i}$ | 3.525
$\chi_{c2}({}^{3}P_{2})$ | $2^{++}$ | $|\epsilon_{ijk}|\gamma_{j}D_{k}$ | 3.556
$\eta_{c2}({}^{1}D_{2})$ | $2^{-+}$ | $\epsilon_{ijk}\gamma_{4}\gamma_{5}\gamma_{j}D_{k}$ | —
— | $1^{-+}$ | $\epsilon_{ijk}\gamma_{j}B_{k}$ | —

In order to extract the masses of charmonium(-like) states and study their
decompositions, we calculate the two-point functions $C_{2}(t)$ involving the
operators in Table 2 and the corresponding three-point functions $C_{3}(t)$
with the insertions of different parts of the Hamiltonian in Eq. (Gluons in
the Charmonium(-like) States). These are done by using wall source operators
in the Coulomb gauge. For the conventional charmonia, $C_{2}(t)$ is obtained
by the expression

$C_{2}(t_{f},\Gamma)=\langle\gamma_{5}S^{\dagger}_{w}(\vec{y},t_{f};0)\gamma_{5}\Gamma
S_{w}(\vec{y},t_{f};0)\Gamma\rangle,$ (5)

where $S_{w}(\vec{y},t_{f};0)=\sum_{\vec{x}}S(\vec{y},t_{f};\vec{x},0)$,
$S(\vec{y},t_{f};\vec{x},0)$ is the quark propagator from $(\vec{x},0)$ to
$(\vec{y},t_{f})$, $\Gamma$ is a specific Dirac gamma matrix combination as
used in Table. 2. Note that the required summation over the spatial indices is
performed implicitly. For the $1^{-+}$ state, one of the $S_{w}$ terms used
above is modified into
$S_{w}^{B_{i}}=\sum_{\vec{x}}S(\vec{y},t_{f};\vec{x},0)B_{i}(\vec{x})$, and
the chromomagentic field strength $B_{k}$ should be inserted in the sink
interpolation field to ensure the correct quantum numbers. The $2^{\pm+}$
state can be obtained similarly using the propagator with a derivative in both
the source and sink interpolation fields.

For the three-point functions relevant to $\langle H_{m}\rangle$ and $\langle
x\rangle_{q}$, we use the summed current sequential source method Chang  _et
al._ (2018) to suppress excited state contamination. To be specific, the
current-summed three-point function is expressed as

$\displaystyle
C_{3}(t_{f},\Gamma,O)=\langle\gamma_{5}S_{w}(\vec{y},t_{f};0)\gamma_{5}\Gamma\tilde{S}_{c}(\vec{y},t_{f};0;O)\Gamma\rangle,$
(6)

where the current sequential propagator $\tilde{S}_{c}(\vec{y},t_{f};0;O)$ is
defined as

$\displaystyle\tilde{S}_{c}(\vec{y},t_{f};0;H_{m})=$ $\displaystyle
m_{c}\sum_{\vec{x},t}S(\vec{y},t_{f};\vec{x},t)S_{w}(\vec{x},t;0),$ (7)
$\displaystyle\tilde{S}_{c}(\vec{y},t_{f};0;x)=$
$\displaystyle\sum_{\vec{x},t}S(\vec{y},t_{f};\vec{x},t)(D_{4}\gamma_{4}-\frac{1}{3}\sum_{i}D_{i}\gamma_{i})$
$\displaystyle\quad S_{w}(\vec{x},t;0),$ (8)

for $O=H_{m}$ and $O=x$, respectively, and $m_{c}$ is the bare charm quark
mass. Finally, from the ratio $R(t_{f},O)\equiv
C_{3}(t_{f},\Gamma,O)/C_{2}(t_{f},\Gamma)$ one can get

$\displaystyle\langle H_{m}\rangle\approx
R(t_{f},H_{m})-R(t_{f}-1,H_{m})~{}~{}~{}(t_{f}\to\infty),$ $\displaystyle
M\langle x\rangle_{q}\approx
R(t_{f},x)-R(t_{f}-1,x)~{}~{}~{}(t_{f}\to\infty).$ (9)

In the $1^{-+}$ channel, we need to replace one of the $S_{w}$ terms in Eq.
(6) by the $S_{w}^{B_{i}}$ (Note that $S_{w}^{B_{i}}$ should be symmetric with
respect to the interchange of spatial coordinates to ensure the correct
$P$-parity).

In each $J^{PC}$ channel, we carry out a joint correlated fit of
$C_{3}(t_{f},H_{m})$, $C_{3}(t_{f},x)$ and $C_{2}(t_{f})$ using the following
function forms,

$\displaystyle C_{3}(t_{f},H_{m})=$ $\displaystyle
e^{-Mt_{f}}\left(C_{0}t_{f}\langle H_{m}\rangle+C_{2}e^{-\delta
mt_{f}}\right.$ $\displaystyle\left.+C_{3}t_{f}e^{-\delta
mt_{f}}+C_{4}\right),$ $\displaystyle C_{3}(t_{f},x)=$ $\displaystyle
e^{-Mt_{f}}\left(C_{0}t_{f}M\langle x\rangle_{q}+C_{5}e^{-\delta
mt_{f}}\right.$ $\displaystyle\left.+C_{6}t_{f}e^{-\delta
mt_{f}}+C_{7}\right),$ $\displaystyle C_{2}(t_{f})=$ $\displaystyle
C_{0}e^{-Mt_{f}}(1+C_{1}e^{-\delta mt_{f}})$
$\displaystyle+W(-1)^{t_{f}}e^{-\tilde{M}t_{f}},$ (10)

where the $e^{-\delta mt_{f}}$ terms are introduced to account for the
contamination from higher states, $\delta m$ and $C_{0,...,7}$ are free
parameters, the $(-1)^{t_{f}}$ term is added to account for the oscillatory
behavior related to domain wall fermion Liang  _et al._ (2014). The hadron
mass $M$, $\langle H_{m}\rangle$ and $\langle x\rangle_{q}$ can be extracted
simultaneously. These functions facilitate us to use data of the correlation
functions at earlier time slices that have much better signal-to-noise ratios
in the fit. It is found that the data can be modeled very well by these
functions and the chi-squares per degree of freedom are usually around one
which signal the good quality of the fit. The details of fitting strategy and
results can be found in the supplemental materials sun .

Based on previous work of proton mass decomposition at several lattice
spacings Yang  _et al._ (2018), the mixing from gluon momentum fraction to
that of quark is at 1% level per flavor and then the quark momentum fraction
is almost multiplicatively renormalizable with its renormalization constant
after normalization to be $Z_{QQ}(\text{32I})=0.99(5)$ at $a$=0.0828(3) fm. We
haven’t obtained $Z_{QQ}$ on 48If yet but $\langle x\rangle_{q}$ on 48If just
differs $\sim$4% from that on 32I. Thus we just present bare $\langle
x\rangle_{q}$ ignoring all the renormalization effects in this exploratory
study.

Results and discussion: The ground state masses of the charmonium(-like)
states considered in this study are obtained using the joint fits with
$\langle H_{m}\rangle$ and $\langle x\rangle_{q}$, and Table 3 collected the
values from the fit in the range of $[t_{\mathrm{min}},t_{\mathrm{max}}]$ and
the $\chi^{2}$/d.o.f.. In Fig. 1, the black and blue boxes illustrate the
results on the 32I and 48If ensembles, respectively, with the heights of the
boxes showing the statistical errors. We have converted the masses to the
values in physical units according to the lattice spacings listed in Table 1.
The experimental values from PDG Zyla  _et al._ (2020) are also plotted in
green lines for comparison. By setting the bare charm quark masses with the
PDG value of the $J/\psi(1^{--})$ mass, our prediction of the hyperfine-
splittings of $J/\psi-\eta_{c}$ on the two ensembles agrees with the PDG value
within 5% difference. The masses of the $\\{1^{+-},(0,1,2)^{++}\\}$ states are
a little lower than those of experimental $1P$ charmonia
$\\{h_{c},\chi_{c0,1,2}\\}$ and have mild finite lattice spacing dependences.
This deviation may be attributed to the discretization uncertainties that have
not been removed in this exploratory study. The ground state mass in $2^{-+}$
channel is determined to be 3.747(44) GeV (32I) and 3.788(30) GeV (48If). Even
though the $2^{-+}$ charmonium which is usually named $\eta_{c2}$ and assigned
to be $1^{1}D_{2}$ state has not been observed in experiments, its mass should
be in this range according to the masses of its spin-triplet partner
$\psi(3770)(1^{3}D_{1})$, $\psi_{2}(3823)(1^{3}D_{2})$ Bhardwaj  _et al._
(2013); Ablikim  _et al._ (2015) and $\psi_{3}(3842)(1^{3}D_{3})$ Aaij  _et
al._ (2019). The $1^{-+}$ state, with an exotic quantum number, is around 4.2
to 4.3 GeV, agrees with the result of the latest lattice QCD calculation with
dynamical quarks Liu  _et al._ (2012).

Figure 1: Ground state mass $M$ of various $J^{PC}$ quantum numbers on
$32^{3}\times 64$ and $48^{3}\times 96$ configurations, the height of color
boxes indicates the statistical errors and the experimental value for $1S$ and
$1P$ states from PDG are shown for comparision.

Figure 2: Ground state $\langle H_{m}\rangle$ and $\langle x\rangle_{q}$ of valence charm quark of various $J^{PC}$ quantum numbers on $32^{3}\times 64$ and $48^{3}\times 96$ configuration. Figure 3: Combined valence charm quark contribution $\langle H_{q}\rangle$ in ground state of various $J^{PC}$ quantum numbers on $32^{3}\times 64$ and $48^{3}\times 96$ configuration, the extracted mass $M$ are also shown for comparision. Table 3: Fitted groud state hadron mass $M$, quark mass contribution $\langle H_{m}\rangle$ and quark momentum fraction $\langle x\rangle_{q}$ in physical units on two ensembles, where the fitting range and $\chi^{2}$/d.o.f. are also shown in the table. | $J^{PC}$ |  $M$(GeV) |  $\langle H_{m}\rangle$(GeV) | $\langle x\rangle_{q}$ | [$t_{min}$ \- $t_{max}$] |  $\chi^{2}$/d.o.f.
---|---|---|---|---|---|---
$32^{3}\times 64$ | $0^{-+}$ | 2.983(01) | 2.212(01) | 0.784(01) | 8 - 23 | 1.46
$1^{--}$ | 3.104(02) | 2.162(02) | 0.810(01) | 8 - 23 | 1.26
$0^{++}$ | 3.375(24) | 2.087(70) | 0.735(22) | 10 - 21 | 1.02
$1^{++}$ | 3.434(11) | 2.101(30) | 0.742(11) | 9 - 22 | 1.20
$1^{+-}$ | 3.441(09) | 2.152(33) | 0.723(12) | 9 - 22 | 1.39
$2^{++}$ | 3.480(08) | 2.100(35) | 0.722(15) | 5 - 16 | 1.02
$2^{-+}$ | 3.747(44) | 2.08(11) | 0.694(32) | 5 - 12 | 0.84
$1^{-+}$ | 4.250(61) | 2.317(53) | 0.553(15) | 3 - 11 | 1.49
$48^{3}\times 96$ | $0^{-+}$ | 2.985(01) | 2.193(01) | 0.761(01) | 10 - 39 | 1.39
$1^{--}$ | 3.100(01) | 2.139(01) | 0.781(01) | 14 - 39 | 1.44
$0^{++}$ | 3.396(17) | 2.113(25) | 0.722(08) | 8 - 22 | 1.50
$1^{++}$ | 3.480(18) | 2.063(38) | 0.741(14) | 10 - 20 | 1.35
$1^{+-}$ | 3.500(14) | 2.030(44) | 0.732(13) | 10 - 20 | 0.97
$2^{++}$ | 3.492(07) | 2.070(17) | 0.710(07) | 5 - 24 | 1.55
$2^{-+}$ | 3.788(30) | 2.019(49) | 0.675(15) | 5 - 17 | 1.33
$1^{-+}$ | 4.296(64) | 2.202(59) | 0.559(19) | 4 - 14 | 0.96

Quark mass contribution $\langle H_{m}\rangle$ in different states are
illutrated in the upper panel of Fig. 2. For all the states, $\langle
H_{m}\rangle$ is around 2.0 to 2.2 GeV. Note that $\langle H_{m}\rangle$ here
only includes the contribution from valence charm quarks. The contribution
from charm sea quarks is subtle since the 2+1 flavor ensemble is used in this
work and we don’t have any charm sea in the configurations, but its
contribution $\langle H_{m}^{c,sea}\rangle$ can be estimated from the charm
valence quark contribution $\langle H_{m}^{c,v}\rangle$ (the actual $\langle
H_{m}\rangle$ we obtained) based on the heavy quark expansion Shifman  _et
al._ (1978),

$\displaystyle\langle
H_{m}^{c,sea}\rangle=\frac{2}{27}\big{(}\frac{1}{1+\gamma_{m}(\mu)}M-\langle
H_{m}^{c,v}\rangle\big{)}+{\cal O}(\alpha_{s}).$ (11)

where $\gamma_{m}(\mu)\approx 2\alpha(\mu)/\pi$ is anomalous dimension of the
quark mass, and if we take $\alpha(\mu=m_{c})\approx 0.37$ Maezawa and
Petreczky (2016), then $\langle H_{m}^{c,sea}\rangle$ is less than 100 MeV for
all these states, therefore we just ignore the charm sea quark contribution in
present study.

The light and strange sea quark contributions to $\langle H_{m}\rangle$ was
estimated by the light quark mass dependence of charmonium masses Yang  _et
al._ (2015), through the Feynman-Hellman theorem. For $u,d$ quarks, the matrix
element $\langle\int d^{3}x\bar{\psi}(x)\psi(x)\rangle$ is approximately 0.3
at $\overline{\textrm{MS}}$ 2 GeV. This quantity for strange quarks should not
be larger. Thus $u,d,s$ sea quark contribution to $\langle H_{m}\rangle$ would
be not larger than 40 MeV in total and can be ignored temporarily.

On the other hand, estimation of the sea quark momentum fraction is relatively
non-trivial. We know that the light sea quark momentum fraction is a few
percent in the nucleon and for the heavy quark it is further suppressed by the
quark mass and then will be even smaller Alexandrou  _et al._ (2020).

According to the relation $M=\langle H_{m}\rangle+\langle H_{a}\rangle$, one
can conclude that the mass differences among $1S$, $1P$, $1D$ charmonia and
$1^{-+}$ charmonium-like state mainly from the contribution of the QCD trace
anomaly part $\langle H_{a}\rangle$. The quark relevant part of $\langle
H_{a}\rangle$ is $\gamma_{m}\langle H_{m}\rangle$ as shown in Eq. (Gluons in
the Charmonium(-like) States). Since $\gamma_{m}(\mu)$ is common for all
states and $\langle H_{m}\rangle$ is scale independent, we can further claim
that the mass differences are dominated by the gluon components of
charmonium(-like) states.

It is interesting to see that, as shown in the lower panel of Fig. 2, the
momentum fraction $\langle x\rangle_{q}$ of the valence charm quark and
antiquark is in the range of 70%-80% and does not change much for conventional
$1S$, $1P$ and $1D$ charmonia, while it is only approximately 55% for the
$1^{-+}$ state. This is a striking difference, which means there is a roughly
20% more momentum fraction carried by other degrees of freedom, such as gluons
and $u,d,s$ sea quarks in the $1^{-+}$ state, in comparison with that of
$J/\psi$ and $\eta_{c}$. This surplus amount of momentum fraction accounts for
approximately 800 MeV of the mass of the $1^{-+}$ state, given its mass around
4.3 GeV. If the $1^{-+}$ state is interpreted phenomenologically as a
$c\bar{c}g$ hybrid, then this portion of mass of 800 MeV is close to the mass
of a constituent gluon in the constituent model for glueballs and hybrids.
However, one should be cautious to make this argument since a $c\bar{c}g$
hybrid is ill-defined in QCD due to gluon-$q\bar{q}$ transition within a
hadron system, which also allows possible $c\bar{c}q\bar{q}\ldots$
configurations. Whatever this $1^{-+}$ charmonium-like state is, the striking
difference of its $\langle x\rangle_{q}$ from the conventional charmonia may
signals its special inner structure.

Moreover, according to Eq. (4), the combined quark contribution $\langle
H_{q}\rangle$ of the valence charm quark can be expressed in terms of $\langle
x\rangle_{q}$ and $\langle H_{m}\rangle$, whose values for different states
are shown in Fig. 3, where the masses of charmonium(-like) states are also
plotted with light color for comparison. It is clearly seen that the $\langle
H_{q}\rangle$ in all the states are close to each other and around 2.3-2.5
GeV. The mass sum rule in Eq. (2) implies again that the gluon contribution to
the masses is $M-\langle H_{q}\rangle$ (except for a small portion
$\frac{1}{4}\gamma_{m}(\mu)\langle H_{m}\rangle)$ that gives the major
differences among charmonium(-like) states.

Summary: We investigated mass decomposition of conventional $1S,1P,1D$
charmonia and exotic $1^{-+}$ charmonium-like state. It is found that quark
mass contribution $\langle H_{m}\rangle$ of valence charm quark is around 2.0
to 2.2 GeV for these states, which implies that the mass splittings among
these states come almost all from the contribution of QCD anomaly and
ultimately the gluon contribution. The valence charm quark momentum fraction
$\langle x\rangle_{q}$ of the $1^{-+}$ state is only around 0.55, while that
in the other conventional charmonia is around 0.7 to 0.8. This difference
manifests that the proportion of light quarks and gluons in the $1^{-+}$
charmonium-like state is significantly larger than that in conventional
states. Our results are helpful to identify charmonium(-like) states
experimentally, and to further clarify their properties.

Acknowledgement: We thank the RBC and UKQCD collaborations for providing us
their DWF gauge configurations. The calculations were performed using the GWU-
code Alexandru  _et al._ (2012, 2011) through HIP programming model Bi  _et
al._ (2020). This work is supported by the National Key Research and
Development Program of China (No.2017YFB0203202), the Strategic Priority
Research Program of Chinese Academy of Sciences (No.XDC01040100 and
XDB34030300), and the Natural Science Foundation of China under grant No.
11935017 and 11975127. The computing resources of the Southern China Nuclear
Computer center (SCNC) and HPC Cluster of ITP-CAS are acknowledged. Y. Chen is
also supported by the CAS Center for Excellence in Particle Physics (CCEPP).
P. Sun is also supported by Jiangsu Specially Appointed Professor Program.

## References

  * Shifman  _et al._ (1978) M. A. Shifman, A. I. Vainshtein, and V. I. Zakharov, Phys. Lett. B78, 443 (1978).
  * Ji (1995) X.-D. Ji, Phys. Rev. Lett. 74, 1071 (1995), arXiv:hep-ph/9410274 [hep-ph] .
  * Yang  _et al._ (2018) Y.-B. Yang, J. Liang, Y.-J. Bi, Y. Chen, T. Draper, K.-F. Liu, and Z. Liu, Phys. Rev. Lett. 121, 212001 (2018), arXiv:1808.08677 [hep-lat] .
  * Lorcé (2018) C. Lorcé, Eur. Phys. J. C78, 120 (2018), arXiv:1706.05853 [hep-ph] .
  * Aoki  _et al._ (2011) Y. Aoki _et al._ (RBC, UKQCD), Phys. Rev. D83, 074508 (2011), arXiv:1011.0892 [hep-lat] .
  * Mawhinney (2019) R. D. Mawhinney (RBC, UKQCD), (2019), arXiv:1912.13150 [hep-lat] .
  * Chiu and Zenkin (1999) T.-W. Chiu and S. V. Zenkin, Phys. Rev. D59, 074501 (1999), arXiv:hep-lat/9806019 [hep-lat] .
  * Zyla  _et al._ (2020) P. A. Zyla _et al._ (Particle Data Group), PTEP 2020, 083C01 (2020).
  * Chang  _et al._ (2018) C. C. Chang _et al._ , Nature 558, 91 (2018), arXiv:1805.12130 [hep-lat] .
  * Liang  _et al._ (2014) J. Liang, Y. Chen, M. Gong, L.-C. Gui, K.-F. Liu, Z. Liu, and Y.-B. Yang, Phys. Rev. D 89, 094507 (2014), arXiv:1310.3532 [hep-lat] .
  * (11) Supplementary materials .
  * Bhardwaj  _et al._ (2013) V. Bhardwaj _et al._ (Belle), Phys. Rev. Lett. 111, 032001 (2013), arXiv:1304.3975 [hep-ex] .
  * Ablikim  _et al._ (2015) M. Ablikim _et al._ (BESIII), Phys. Rev. Lett. 115, 011803 (2015), arXiv:1503.08203 [hep-ex] .
  * Aaij  _et al._ (2019) R. Aaij _et al._ (LHCb), JHEP 07, 035 (2019), arXiv:1903.12240 [hep-ex] .
  * Liu  _et al._ (2012) L. Liu, G. Moir, M. Peardon, S. M. Ryan, C. E. Thomas, P. Vilaseca, J. J. Dudek, R. G. Edwards, B. Joo, and D. G. Richards (Hadron Spectrum), JHEP 07, 126 (2012), arXiv:1204.5425 [hep-ph] .
  * Maezawa and Petreczky (2016) Y. Maezawa and P. Petreczky, Phys. Rev. D 94, 034507 (2016), arXiv:1606.08798 [hep-lat] .
  * Yang  _et al._ (2015) Y.-B. Yang _et al._ , Phys. Rev. D92, 034517 (2015), arXiv:1410.3343 [hep-lat] .
  * Alexandrou  _et al._ (2020) C. Alexandrou, S. Bacchio, M. Constantinou, J. Finkenrath, K. Hadjiyiannakou, K. Jansen, G. Koutsou, H. Panagopoulos, and G. Spanoudes, Phys. Rev. D101, 094513 (2020), arXiv:2003.08486 [hep-lat] .
  * Alexandru  _et al._ (2012) A. Alexandru, C. Pelissier, B. Gamari, and F. Lee, J. Comput. Phys. 231, 1866 (2012), arXiv:1103.5103 [hep-lat] .
  * Alexandru  _et al._ (2011) A. Alexandru, M. Lujan, C. Pelissier, B. Gamari, and F. X. Lee, in  _Proceedings, 2011 Symposium on Application Accelerators in High-Performance Computing (SAAHPC’11): Knoxville, Tennessee, July 19-20, 2011_ (2011) pp. 123–130, arXiv:1106.4964 [hep-lat] .
  * Bi  _et al._ (2020) Y.-J. Bi, Y. Xiao, W.-Y. Guo, M. Gong, P. Sun, S. Xu, and Y.-B. Yang,  _Proceedings, 37th International Symposium on Lattice Field Theory (Lattice 2019): Wuhan, China, June 16-22 2019_ , PoS LATTICE2019, 286 (2020), arXiv:2001.05706 [hep-lat] .

## Supplemental materials

###  .1 Fitting Strategy

We use the parameterization of Eq. (Gluons in the Charmonium(-like) States) in
the paper to fit the simulated data. The two states simultaneous correlated
least chi-square fit is used to account for the excited state contamination
and the hadron mass $M$, quark mass contribution $\langle H_{m}\rangle$, quark
momentum fraction $\langle x\rangle_{q}$ can be extracted simultaneously.
Firstly, the effective mass from two-point function is defined as

$M_{eff}(t_{f})\equiv\ln\frac{C_{2}(t_{f},\Gamma)}{C_{2}(t_{f}+1,\Gamma)}\
_{\overrightarrow{t_{f}\rightarrow\infty}}M,$ (12)

then with best fit parameters in Eq. (Gluons in the Charmonium(-like) States),
we show the effective mass, effective matrix element $\langle H_{m}\rangle$
and $\langle x\rangle_{q}$ as defined in Eq. (Gluons in the Charmonium(-like)
States) in Fig. 4, 5, 6 respectively, where the data points are simulated data
with jackknife estimated error, the light color band shows the fitted result
with best fit parameters, and the dark color band shows the fitting range we
used, the results are converted into physical units with the lattice spacing
shown in Table. 1 and the fit details are shown in Table. 3 in the paper.

Figure 4: Effective mass (points) from simulation data and effective mass
(color band) as defined in Eq. (12) with best fit parameters in $C_{2}$ of
various $J^{PC}$ quantum numbers on $32^{3}\times 64$ (top) and $48^{3}\times
96$ (bottom) configuration. The points with errorbar are simulated data with
jackknife estimated error, the light color band shows the fitted result with
best fit parameters, and the dark color band shows the fitting range.

Figure 5: Same as Fig. 4, but for effective matrix element of valence charm
quark mass contribution $\langle H_{m}\rangle$.

Figure 6: Same as Fig. 4, but for effective matrix element of valence charm
quark momentum fraction $\langle x\rangle_{q}$.