# Inequalities for $k$-regular partitions

Bernhard Heim  Department of Mathematics and Computer Science
Division of Mathematics
University of Cologne
Weyertal 86–90
50931 Cologne
Germany  Lehrstuhl A für Mathematik, RWTH Aachen University, 52056 Aachen,
Germany<EMAIL_ADDRESS>and  Markus Neuhauser  Kutaisi International
University, 5/7, Youth Avenue, Kutaisi, 4600 Georgia  Lehrstuhl A für
Mathematik, RWTH Aachen University, 52056 Aachen, Germany
<EMAIL_ADDRESS>
###### Abstract.

We build upon the work by Bessenrodt and Ono, as well as Beckwith and
Bessenrodt concerning the combined additive and multiplicative behavior of the
$k$-regular partition functions $p_{k}(n)$. Our focus is on addressing the
solutions of the Bessenrodt–Ono inequality

$p_{k}(a)\,p_{k}(b)>p_{k}(a+b).$

We determine the sets $E_{k}$ and $F_{k}$ consisting of all pairs $(a,b)$,
where we have equality or the opposite inequality. Bessenrodt and Ono
previously determined the exception sets $E_{\infty}$ and $F_{\infty}$ for the
partition function $p(n)$. We prove by induction that $E_{k}=E_{\infty}$ and
$F_{k}=F_{\infty}$ if and only if $k\geq 10$. Beckwith and Bessenrodt used
analytic methods to consider $2\leq k\leq 6$, while Alanazi, Gagola, and
Munagi studied the case $k=2$ using combinatorial methods. Finally, we present
a precise and comprehensive conjecture on the log-concavity of the $k$-regular
partition function extending previous speculations by Craig and Pun. The case
$k=2$ was recently proven by Dong and Ji.

###### Key words and phrases:

Bessenrodt–Ono inequality, Generating functions, $k$-regular partitions.

###### 2020 Mathematics Subject Classification:

Primary 05A17, 11P82; Secondary 05A20

##  1\. Introduction

In this paper we investigate partition functions [An98, On04] and provide a
complete solution for the Bessenrodt–Ono inequality [BO16] for $k$-regular
partition functions $p_{k}(n)$ [Ha71]. We extend the previous results for
$2\leq k\leq 6$ by Beckwith and Bessenrodt [BB16] to $k\geq 2$, proving that
for $k\geq 10$, the solutions coincide with the solutions of the partition
function $p(n)$.

Let $\\{\alpha(n)\\}_{n}$ denote a sequence of positive integers. The sequence
satisfies the Bessenrodt–Ono inequality for a pair $(a,b)$ of positive
integers if

(1.1) $\Delta(a,b):=\alpha(a)\,\alpha(b)-\alpha(a+b)>0.$

For partitions $\alpha(0)=\alpha(1)=1$ and due to symmetry, we only consider
pairs with $1<a\leq b$. Let $E$ denote the set of pairs where $\Delta(a,b)=0$
and $F$ the set, where $\Delta(a,b)<0$. For $k$-regular partition functions,
we use the symbols $\Delta_{k}(a,b)$, $E_{k}$ and $F_{k}$, where
$k\in\\{2,3,4,\ldots\\}\cup\\{\infty\\}$.

Let us recall the definition of the $k$-regular partition function $p_{k}(n)$.
A partition of a positive integer $n$ is a finite nonincreasing sequence of
positive integers that sum to $n$. These integers are called the parts of the
partition. The partition function $p(n)$ is the number of partitions of $n$
([An98], Section 1.1). Let $k\geq 2$. The $k$-regular partition function
$p_{k}(n)$ is the number of partitions of $n$ in which none of the parts is a
multiple of $k$. Note, that $p_{k}(n)$ is also equal to the number of
partitions with each part appearing at most $k-1$ times. Therefore, the number
of partitions of $n$ with odd parts is equal to the number of partitions with
different parts. Based on the results of this paper and the fact that
$p_{k}(n)=p(n)$ for $k>n$, we define $p_{\infty}(n):=p(n)$.

In 2016, Bessenrodt and Ono [BO16] discovered the following property of the
partition function $p_{\infty}(n)$.

######  Theorem 1.1 (Bessenrodt, Ono 2016).

Let $1<a\leq b$. Then the Bessenrodt–Ono inequality (1.1) is satisfied for the
partition function $p_{\infty}(n)$, except for the pairs

$\displaystyle E_{\infty}$ $\displaystyle=$
$\displaystyle\left\\{\left(2,6\right),\left(2,7\right),\left(3,4\right)\right\\},$
$\displaystyle F_{\infty}$ $\displaystyle=$
$\displaystyle\\{(2,2),(2,3),(2,4),(2,5),(3,3),(3,5)\\}.$

Bessenrodt and Ono provided an analytic proof ([BO16], Section 2) utilizing
deep results by Lehmer [Le39] and Rademacher [Ra37] for the partition
function, built on the circle method by Hardy and Ramanujan. A second
combinatorial proof was found by Alanazi, Gagola, and Munagi [AGM17]. Their
sophisticated proof involved an injective map and an induction. A third
algebraic proof was provided in [HN22] using induction, and was also
generalized to plane partitions [HNT23].

Beckwith and Bessenrodt [BB16] demonstrated that $k$-regular partition
functions for $2\leq k\leq 6$ also fulfill the Bessenrodt–Ono inequality (see
Section 2 for their result).

Moreover, many more sequences turned out to satisfy (1.1). Chern, Fu, and Tang
[CFT18] generalized and proved the Bessenrodt–Ono inequality (BO) for
$k$-colored partitions. Hou and Jagadeesan [HJ18] extended on the numbers of
partitions with ranks in a given residue class modulo $3$ and Males [Ma20] did
so for general modulus. A modified BO was presented in [HN19]. Dawsey and
Masri [DM19] proved BO for the Andrews spt-function, and Gajdzica did so for
$A$-partitions. In [HNT20], the polynomization of the $k$-colored partitions
[CFT18] was initiated, leading to a continous version of the Chern, Fu, Tang
result [CFT18] for $k$-regular partitions. The proof is utilizing an Euler-
type recursion formula for the involved polynomials and their derivatives.
This polynomization approach and the underlying proof strategy were also
successfully applied by Li [Li23] for the overpartition function and by
Gajdzica et al. ([GHN24], Theorem 1.3) for $A$-partition functions.

Recently, several interesting and important papers have explored the
asymptotic behavior leading to log-concavity properties and the Bessenrodt–Ono
inequality, as well as their relations. We refer to Bringmann, Franke, and
Heim ([BFH24], Theorem 1.3 and Theorem 1.5), Benfield and Roy ([BR24], Theorem
1.1) and Gajdzica, Miska, and Ulas ([GMU24], Theorem 2.1 and Theorem 3.1).

##  2\. Results on $k$-regular partitions

Let $k\geq 2$. The generating function for the number of $k$-regular
partitions is given by

$\sum_{n=0}^{\infty}p_{k}(n)\,q^{n}=\prod_{n=1}^{\infty}\frac{\left(1-q^{kn}\right)}{\left(1-q^{n}\right)}.$

Note that

$\prod_{n=1}^{\infty}\frac{\left(1-q^{2n}\right)}{\left(1-q^{n}\right)}=\prod_{n=1}^{\infty}\left(1-q^{2n-1}\right)^{-1},$

which implies that the number of $2$-regular partitions of $n$ is equal to the
number of partitions of $n$ with odd parts. We also refer to Glaisher’s
generalization for arbitrary $k$ ([An98], Corollary 1.3).

Let $g_{k}(n):=\sigma(n)-k\sigma(n/k)$, where $\sigma(n):=\sum_{d\mid n}d$ and
$\sigma(x)=0$ if $x\not\in\mathbb{N}$. Then

$\sum_{n=0}^{\infty}p_{k}\left(n\right)q^{n}=\exp\left(\sum_{n=1}^{\infty}g_{k}(n)\,\frac{q^{n}}{n}\right).$

This follows from the identity
$\prod_{n=1}^{\infty}\left(1-q^{n}\right)=\exp\left(-\sum_{n=1}^{\infty}\sigma(n)\,q^{n}/n\right)$
and implies

$n\,p_{k}(n)=\sum_{\ell=1}^{n}g_{k}(\ell)\,p_{k}(n-\ell),$

with initial value $p_{k}(0)=1$. Beckwith and Bessenrodt proved, in the same
spirit as [BO16], that the $k$-regular partition function for $2\leq k\leq 6$
satisfies (1.1). They utilized a Rademacher-type formula for $p_{k}(n)$ given
by Hagis [Ha71] and determined for each $k$ the exception sets $E_{k}$ and
$F_{k}$. We recall the following: Let $a,b,k$ be positive integers with
$1<a\leq b$ and let $k\geq 2$. Then we denote by $E_{k}$ the set of all pairs
$(a,b)$ with equality in (1.1) and $F_{k}$ the set of all pairs $(a,b)$ with

$p_{k}(a)\,p_{k}(b)<p_{k}(a+b).$

$k$ |  Elements of $E_{k}$ |  Elements of $F_{k}$
---|---|---
$2$ |  $\left(3,3\right)$, $\left(3,5\right)$, $\left(3,6\right)$, $\left(3,7\right)$, $\left(3,8\right)$, $\left(4,15\right)$, $\left(4,16\right)$, $\left(4,17\right)$, $\left(5,6\right)$, $\left(5,7\right)$, $\left(5,8\right)$ |  $\left(2,b\right)$, $b\geq 2$, $\left(3,4\right)$, $\left(4,4\right)$, $\left(4,5\right)$, $\left(4,6\right)$, $\left(4,7\right)$, $\left(4,8\right)$, $\left(4,9\right)$, $\left(4,10\right)$, $\left(4,11\right)$, $\left(4,12\right)$, $\left(4,13\right)$, $\left(4,14\right)$, $\left(5,5\right)$
$3$ |  $\left(2,2\right)$, $\left(3,10\right)$ |  $\left(2,3\right)$, $\left(3,3\right)$, $\left(3,4\right)$, $\left(3,5\right)$, $\left(3,6\right)$, $\left(3,7\right)$, $\left(3,8\right)$, $\left(3,9\right)$, $\left(3,11\right)$, $\left(3,13\right)$
$4$ |  $\left(2,2\right)$, $\left(2,3\right)$, $\left(2,5\right)$, $\left(3,3\right)$, $\left(3,4\right)$, $\left(4,4\right)$ |  $\left(2,4\right)$
$5$ |  $\left(2,3\right)$, $\left(2,4\right)$ |  $\left(2,2\right)$, $\left(2,5\right)$, $\left(3,3\right)$, $\left(3,5\right)$
$6$ |  $\left(2,4\right)$, $\left(2,5\right)$, $\left(2,6\right)$ |  $\left(2,2\right)$, $\left(2,3\right)$, $\left(3,3\right)$
Table 1. Exceptions to the Bessenrodt–Ono inequality
for $2\leq k\leq 6$

######  Theorem 2.1 (Beckwith, Bessenroth 2016).

Let $a,b,k$ be integers with $1<a\leq b$ and $2\leq k\leq 6$. Then the
Bessenrodt–Ono inequality

(2.1) $p_{k}(a)\,p_{k}(b)>p_{k}(a+b)$

is satisfied for all pairs, except for the pairs presented in Table 1 for
$E_{k}$ and $F_{k}$. Therefore, let $n_{k}$ and $m_{k}$ be given by the
following table:

$\begin{array}[]{|c|c|c|c|c|c|}\hline\cr k&2&3&4&5&6\\\ \hline\cr
n_{k}&3&2&2&2&2\\\ m_{k}&22&17&9&9&9\\\ \hline\cr\end{array}$

Then for any $a,b\geq n_{k}$ and $a+b\geq m_{k}$, the Bessenrodt–Ono
inequality (2.1) is valid.

Further, Alanzi, Gagola, and Munagi [AGM17] demonstrated that their
combinatorial proof of the Bessenrodt–Ono inequality can, in principle, be
adapted to the $k$-regular case. They provided a proof for $k=2$ and indicated
that the number of cases increase rapidly for larger $k$.

We extend the table of Beckwith and Bessenrodt for $E_{k}$ and $F_{k}$ to
$7\leq k\leq 10$. This leads to Table 2.

$\begin{array}[]{|r|l|l|}\hline\cr k&\text{Elements of }E_{k}&\text{Elements
of }F_{k}\\\ \hline\cr 7&(2,5),(2,7),(3,5)&(2,2),(2,3),(2,4),(3,3)\\\
8&(3,4),(3,5)&(2,2),(2,3),(2,4),(2,5),(3,3)\\\
9&(2,6),(3,4)&(2,2),(2,3),(2,4),(2,5),(3,3),(3,5)\\\
10&(2,6),(2,7),(3,4)&(2,2),(2,3),(2,4),(2,5),(3,3),(3,5)\\\
\hline\cr\end{array}$ Table 2.  Exceptions to the Bessenrodt–Ono inequality
for $7\leq k\leq 10$

We observe that $E_{k}=E_{\infty}$ and $F_{k}=F_{\infty}$ for $k=10$ and prove
that this even holds true for all $k\geq 10$.

######  Theorem 2.2.

Let $a,b,k\geq 2$ be integers, and $p_{k}(n)$ be the $k$-regular partition
function. Then the Bessenrodt–Ono inequality

$p_{k}(a)\,p_{k}(b)>p_{k}(a+b)$

holds true for all pairs $(a,b)$ except for pairs in $E_{k}$, where equality
is in place and $F_{k}$, where $p_{k}(a)\,p_{k}(b)<p_{k}(a+b)$. For $2\leq
k\leq 10$, the sets $E_{k}$ and $F_{k}$ are given by Tables 1 and 2. For all
$k\geq 10$ we have

$E_{k}=E_{\infty}\text{ and }F_{k}=F_{\infty}.$

##  3\. Proof of Theorem 2.2

We closely follow the proof scheme ([HN22], Section $2$) proposed to prove
Bessenrodt–Ono inequalities.

First, we estimate the arithmetic function $g_{k}(n)$ and the $k$-regular
partition function $p_{k}(n)$ with the following upper and lower bounds,
independent of $k$.

######  Lemma.

Let $k\geq 2$. Then

$\displaystyle g_{k}(n)$ $\displaystyle\leq$ $\displaystyle
n\,\big{(}1+\mathop{\rm ln}(n)\big{)},$ (3.1) $\displaystyle p_{k}(n)$
$\displaystyle>$ $\displaystyle 2^{\sqrt{2n/3+1/4}-3/2}.$

###### Proof.

The upper bound for $g_{k}(n)\leq\sigma(n)$ follows easily by integral
comparison with the bound for $n>1$. The lower bound of $p_{k}(n)$ cannot be
directly related to $p(n)$ as given in ([HN22], equation (2.2)), and requires
some additional investigation.

The lower bound of $p_{k}(n)$ follows from

$p_{k}\left(n\right)\geq
4^{\left\lfloor\sqrt{2n/3+1/2}-1/2\right\rfloor-\left\lfloor\left\lfloor\sqrt{2n/3+1/4}-1/2\right\rfloor/k\right\rfloor}>4^{\left(k-1\right)\left(\sqrt{2n/3+1/4}-3/2\right)/k}.$

Here $\lfloor x\rfloor$ denotes the usual floor symbol. Consider partitions of
$n$ using only parts from
$\left\\{1,2,\ldots,\left\lfloor\sqrt{n/3}\right\rfloor\right\\}\setminus
k\,\,\mathbb{N}$ with multiplicity at most $3$. To any admissible submultiset,
we can assign a partition. The largest value we obtain is

$\displaystyle 3\sum_{m=1}^{\left\lfloor\sqrt{2n/3+1/4}-1/2\right\rfloor}m$
$\displaystyle\leq$
$\displaystyle\frac{3}{2}\left(\sqrt{2n/3+1/4}-1/2+1\right)\left(\sqrt{2n/3+1/4}-1/2\right)$
$\displaystyle=$ $\displaystyle 3\frac{2n/3+1/4-1/4}{2}=n.$

Also, we have removed
$\left\lfloor\frac{1}{k}\left\lfloor\sqrt{\frac{2n}{3}+\frac{1}{4}}-\frac{3}{2}\right\rfloor\right\rfloor$
elements from the set. This demonstrates the claim. ∎

######  Remark.

Note that the proof shows that we could even choose as a lower bound

$p_{k}(n)\geq 2^{\left\lfloor\sqrt{2n/3+1/4}-1/2\right\rfloor}.$

###  3.1. Proof of Theorem 2.2 for $k>3$

Let $A:=2$ and $B:=10$. Let $n\geq B$. We say the statement $S(n)$ holds true
if for all partitions $n=a+b$ with $a,b\geq A$:

$\Delta_{k}(a,b):=p_{k}(a)\,p_{k}(b)-p_{k}(a+b)>0.$

We assume that $n>N_{0}>1$ and $S(m)$ hold true for all $B\leq m\leq n-1$. For
$B\leq m\leq N_{0}$, we demonstrate $S(m)$ through a direct computer
calculation with PARI/GP. It will turn out that we can choose $N_{0}=2938$.

We obtain the following expressions for $\Delta_{k}\left(a,b\right)=L+R$:

$\displaystyle L$ $\displaystyle:=$
$\displaystyle-\sum_{\ell=1}^{b}\frac{g_{k}\left(\ell+a\right)}{a+b}p_{k}\left(b-\ell\right),$
$\displaystyle R$ $\displaystyle:=$
$\displaystyle\sum_{\ell=1}^{a}\Big{(}\frac{g_{k}(\ell)}{a}\,p_{k}(a-\ell)\,p_{k}(b)-\frac{g_{k}(\ell)}{a+b}\,p_{k}(a+b-\ell)\Big{)}.$

Further, we will refine the right sum $R$ into

$R=R_{1}+R_{2}+R_{3}.$

####  3.1.1. Left sum $L$

We have $L>-b\,\,p_{k}\left(b\right)\,\big{(}1+\ln(a+b)\big{)}.$

####  3.1.2. Right sum $R$

Let

$\ell_{0}:=a-\max\left\\{B-b,A\right\\}+1.$

Therefore, $\ell_{0}=a-\max\left\\{9-b,1\right\\}$. Let

$\displaystyle R_{1}$ $\displaystyle:=$
$\displaystyle\sum_{\ell=1}^{1}\,f_{\ell}(a,b),\,\,R_{2}:=\sum_{\ell=2}^{\ell_{0}-1}\,f_{\ell}(a,b),\,\,R_{3}:=\sum_{\ell=\ell_{0}}^{a}\,f_{\ell}(a,b),$
$\displaystyle f_{\ell}(a,b)$ $\displaystyle:=$
$\displaystyle\frac{g_{k}(\ell)}{a}\,p_{k}(a-\ell)\,p_{k}(b)-\frac{g_{k}(\ell)}{a+b}\,p_{k}(a+b-\ell).$

##### The sum $R_{1}$

We obtain the lower bound:

$R_{1}>\frac{b}{2a^{2}}\,p_{k}\left(a-1\right)p_{k}\left(b\right).$

##### The sum $R_{2}$

The second sum: $R_{2}>0$.

##### The sum $R_{3}$

We split the third sum again into three parts: $R_{3}=R_{31}+R_{32}+R_{33}$,
where

(3.2) $\displaystyle R_{31}:=\sum_{\ell=\ell_{0}}^{a-A}\,f_{\ell}(a,b)$
$\displaystyle>$ $\displaystyle
5\,\left(4-p_{\infty}\left(8\right)\right)\,\left(1+\ln\left(a\right)\right),$
$\displaystyle R_{32}:=\sum_{\ell=a-A+1}^{a-1}\,f_{\ell}(a,b)$
$\displaystyle>$ $\displaystyle-
p_{k}\left(b\right)\,\big{(}1+\ln\left(a\right)\big{)},$ $\displaystyle
R_{33}:=\sum_{\ell=a}^{a}\,f_{\ell}(a,b)$ $\displaystyle\geq$ $\displaystyle
0.$

We first use that $p_{k}\left(9-b\right)p_{k}\left(b\right)\geq
p_{k}\left(9\right)$, which leads to at most $5$ summands. The estimation in
(3.2) follows from $p_{k}(a-\ell)\geq p_{k}(2)$. For the estimation, we use
that

$p_{k}\left(b\right)\geq
p_{k}\left(2\right)=2,\,\,\frac{1}{a+b}<\frac{1}{a},\text{ and
}p_{k}(a+b-\ell)\leq p_{k}\left(8\right)\leq p_{\infty}\left(8\right).$

We obtain

$R_{3}>-23\,b\,\,p_{k}\left(b\right)\left(1+\ln\left(a+b\right)\right).$

####  3.1.3. Final step

Putting everything together leads to:

(3.3)
$\Delta_{k}\left(a,b\right)>\frac{b\,p_{k}\left(b\right)}{2\,a^{2}}\left(-48\,a^{2}\,\left(1+\ln\left(2a\right)\right)+2^{\sqrt{2\left(a-1\right)/3+1/4}-3/2}\right).$

As the final step, we used the property (3.1). For $a\rightarrow\infty$ we can
immediately observe that this is positive since the second term grows in $a$
faster than $a\mapsto a^{2}\left(1+\ln\left(2a\right)\right)$. In fact, the
expression (3.3) is positive for all $a\geq 1470$. Note that if $a<1470$, then
$a+b\leq 2a\leq N_{0}$.

Note that for $k>N_{0}$, we have
$p_{k}\left(n\right)=p_{\infty}\left(n\right)$ for all $n\leq N_{0}$.
Therefore, we only have to check the inequality for $k\leq N_{0}$ and $n\leq
N_{0}$. Hence, $\Delta_{k}\left(a,b\right)>0$, which proves the Theorem.

######  Remark.

Note that we can also prove the cases $k\in\left\\{2,3\right\\}$ directly with
our method from [HN22], but then more adjustments are necessary as we cannot
directly use ([HN22], (2.8)) anymore. For $k=2$, we can choose $A=3$ and
$B=22$ with $N_{0}=3662$, and for $k=3$, we can choose $A=2$ and $B=17$ with
$N_{0}=3776$. The crucial step is to adjust the estimate of $R_{31}$ in (3.2)
for these cases.

##  4\. Log-concavity

In this final section, we provide further evidence, that the $k$-regular
partition function and the partition function $p_{\infty}(n)$ share similar
properties up to small $k$s. We indicate that, as in the case of the
Bessenrodt–Ono inequality, this may also apply to the log-concave property.
Nicolas [Ni78] and DeSalvo and Pak [DP15] proved that the partition function
$p_{\infty}(n)$ is log-concave at $n$:

$p(n)_{\infty}^{2}\geq p_{\infty}(n-1)\,p_{\infty}(n+1)$

if and only if $n\geq 25$ or $n$ is even. For $k$-regular partitions, building
on Hagis’ Rademacher-type formula and a new method developed by Griffin, Ono,
Rolen, and Zagier [GORZ19], Craig and Pun [CP20] proved that the $k$-regular
partition functions $p_{k}(n)$ satisfy higher-order Turán inequalities for
sufficiently large $n$ dependent on $k$. Let $N_{k}$ be the smallest number,
such that $\\{p_{k}(n)\\}_{n}$ is log-concave at $n$

$p_{k}(n)^{2}\geq p_{k}(n-1)\,p_{k}\left(n+1\right)$

for all $n\geq N_{k}$. We calculated all exceptions for $2\leq k\leq 100$ and
$1\leq n\leq 1000$. For $2\leq k\leq 20$, we have provided them in Table 3,
where for $k=3$, the exceptions are all odd $1\leq n\leq 57$. This is
compatible with the numbers conjectured by Craig and Pun ([CP21], Remark 1.3)
for $2\leq k\leq 4$. Recently, Dong and Ji [DJ24] proved the conjecture for
$k=2$.

Similar to the Bessenrodt–Ono inequality, we believe that the set of
exceptions stabilizes for large $k$ and is the same as the one of
$p_{\infty}(n)$. This set is given by all odd numbers $1\leq n\leq 25$. We put
$N_{\infty}:=26$.

######  Conjecture.

Let $k\geq 2$. Let $N_{k}$ be the smallest integer, such that
$\\{p_{k}(n)\\}_{n}$ is log-concave at every $n\geq N_{k}$. Then
$N_{k}=N_{\infty}$ if $k\geq 30$.

This is in accordance with Remark 1.3 given by Craig and Pun [CP21]. Since
$p_{k}(n)=p_{\infty}(n)$ for $k>n$ we also have:

######  Corollary.

Let the conjecture hold true. Let $k\geq 30$. Then the exceptions $n$ are the
same as for $\left\\{p_{\infty}(n)\right\\}_{n}$.

$\begin{array}[]{rrrrrrrrrrrrrrrrrrrr}\hline\cr\hline\cr n\backslash
k&2&3&4&5&6&7&8&9&10&11&12&13&14&15&16&17&18&19&20\\\ \hline\cr
1&&\bullet&\bullet&\bullet&\bullet&\bullet&\bullet&\bullet&\bullet&\bullet&\bullet&\bullet&\bullet&\bullet&\bullet&\bullet&\bullet&\bullet&\bullet\\\
2&\bullet&&&&&&&&&&&&&&&&&&\\\
3&&\bullet&&\bullet&\bullet&\bullet&\bullet&\bullet&\bullet&\bullet&\bullet&\bullet&\bullet&\bullet&\bullet&\bullet&\bullet&\bullet&\bullet\\\
4&\bullet&&\bullet&&&&&&&&&&&&&&&&\\\
5&&\bullet&&\bullet&\bullet&\bullet&\bullet&\bullet&\bullet&\bullet&\bullet&\bullet&\bullet&\bullet&\bullet&\bullet&\bullet&\bullet&\bullet\\\
6&&&&&&&&&&&&&&&&&&&\\\
7&&\bullet&&\bullet&\bullet&\bullet&\bullet&\bullet&\bullet&\bullet&\bullet&\bullet&\bullet&\bullet&\bullet&\bullet&\bullet&\bullet&\bullet\\\
8&\bullet&&\bullet&&&&&&&&&&&&&&&&\\\
9&&\bullet&&\bullet&\bullet&\bullet&&\bullet&\bullet&\bullet&\bullet&\bullet&\bullet&\bullet&\bullet&\bullet&\bullet&\bullet&\bullet\\\
10&&&&&&&&&&&&&&&&&&&\\\
11&\bullet&\bullet&\bullet&\bullet&\bullet&\bullet&\bullet&\bullet&\bullet&\bullet&\bullet&\bullet&\bullet&\bullet&\bullet&\bullet&\bullet&\bullet&\bullet\\\
12&&&&&&&&&&&&&&&&&&&\\\
13&\bullet&\bullet&\bullet&\bullet&&\bullet&\bullet&\bullet&\bullet&\bullet&\bullet&\bullet&\bullet&\bullet&\bullet&\bullet&\bullet&\bullet&\bullet\\\
14&\bullet&&&&&&&&&&&&&&&&&&\\\
15&&\bullet&&\bullet&&\bullet&&\bullet&\bullet&\bullet&\bullet&\bullet&\bullet&\bullet&\bullet&\bullet&\bullet&\bullet&\bullet\\\
16&\bullet&&\bullet&&&&&&&&&&&&&&&&\\\
17&\bullet&\bullet&&\bullet&&\bullet&\bullet&\bullet&\bullet&\bullet&\bullet&\bullet&\bullet&\bullet&\bullet&\bullet&\bullet&\bullet&\bullet\\\
18&&&&&&&&&&&&&&&&&&&\\\
19&\bullet&\bullet&&\bullet&&\bullet&\bullet&\bullet&\bullet&\bullet&\bullet&\bullet&\bullet&\bullet&\bullet&\bullet&\bullet&\bullet&\bullet\\\
20&\bullet&&&&&&&&&&&&&&&&&&\\\
21&&\bullet&&\bullet&&\bullet&&\bullet&&\bullet&\bullet&\bullet&&\bullet&\bullet&\bullet&\bullet&\bullet&\bullet\\\
22&&&&&&&&&&&&&&&&&&&\\\
23&\bullet&\bullet&&\bullet&&\bullet&&\bullet&&\bullet&&\bullet&\bullet&\bullet&\bullet&\bullet&\bullet&\bullet&\bullet\\\
24&&&&&&&&&&&&&&&&&&&\\\
25&&\bullet&&\bullet&&\bullet&&\bullet&&\bullet&&\bullet&&\bullet&\bullet&\bullet&\bullet&\bullet&\bullet\\\
26&\bullet&&&&&&&&&&&&&&&&&&\\\
27&&\bullet&&\bullet&&\bullet&&\bullet&&\bullet&&\bullet&&\bullet&&\bullet&&\bullet&\\\
28&&&&&&&&&&&&&&&&&&&\\\
29&\bullet&\bullet&&\bullet&&\bullet&&\bullet&&\bullet&&\bullet&&\bullet&&\bullet&&\bullet&\\\
30&&&&&&&&&&&&&&&&&&&\\\
31&&\bullet&&\bullet&&\bullet&&\bullet&&\bullet&&\bullet&&&&&&&\\\
32&\bullet&&&&&&&&&&&&&&&&&&\\\
33&&\bullet&&\bullet&&\bullet&&\bullet&&&&&&&&&&&\\\ 34&&&&&&&&&&&&&&&&&&&\\\
35&&\bullet&&\bullet&&\bullet&&&&&&&&&&&&&\\\ 36&&&&&&&&&&&&&&&&&&&\\\
37&&\bullet&&\bullet&&&&&&&&&&&&&&&\\\ 38&&&&&&&&&&&&&&&&&&&\\\
39&&\bullet&&\bullet&&&&&&&&&&&&&&&\\\ 40&&&&&&&&&&&&&&&&&&&\\\
41&&\bullet&&\bullet&&&&&&&&&&&&&&&\\\ 42&&&&&&&&&&&&&&&&&&&\\\
43&&\bullet&&&&&&&&&&&&&&&&&\\\ 44&&&&&&&&&&&&&&&&&&&\\\
45&&\bullet&&&&&&&&&&&&&&&&&\\\ \hline\cr\hline\cr\end{array}$
Table 3. Exceptions of log-concavity at $n$ for $2\leq k\leq 20$ and $1\leq
n\leq 45$

## References

  * [AGM17] A. A. Alanazi, S. M. Gagola III, A. O. Munagi: _Combinatorial proof of a partition inequality of Bessenrodt–Ono._ Ann. Comb. 21 (2017), 331–337.
  * [An98] G. E. Andrews: The Theory of Partitions. Cambridge Univ. Press, Cambridge (1998).
  * [BB16] O. Beckwith, C. Bessenrodt: _Multiplicative properties of the number of $k$-regular partitions._ Ann. Comb. 20 No. 2 (2016), 231–250.
  * [BR24] B. Benfield, A. Roy: _Log-concavity and the multiplicative properties of restricted partition functions._ arXiv:2404.03153 (2024).
  * [BO16] C. Bessenrodt, K. Ono: _Maximal multiplicative properties of partitions._ Ann. Comb. 20 No. 1 (2016), 59–64.
  * [BFH24] K. Bringmann, J. Franke, B. Heim: _Asymptotics of commuting $\ell$-tuples in symmetric groups and log-concavity._ arXiv:2401.05874v1 (2024).
  * [CFT18] S. Chern, S. Fu, D. Tang: _Some inequalities for $k$-colored partition functions._ Ramanujan J. 46 (2018), 713–725.
  * [CP20] W. Craig, A. Pun: _Higher order Turán inequalities for $k$-regular partitions._ Séminaire Loth. de Comb. 84B Article #23 (2020).
  * [CP21] W. Craig, A. Pun: _A note on the higher order Turán inequalities for $k$-regular partitions._ Research in Number Theory 7 Article #5 (2021).
  * [DM19] M. L. Dawsey, R. Masri: _Effective bounds for the Andrews spt-function._ Forum Math. 31 No. 3 (2019), 743–767.
  * [DP15] S. DeSalvo, I. Pak: _Log-concavity of the partition function._ Ramanujan J. 38 (2015), 61–73.
  * [DJ24] J. Dong, K. Ji: _Higher order Turán inequalities for the distinct partition function._ Journal of Number Theory 260 (2024), 71–102.
  * [GHN24] K. Gajdzica, B. Heim, M. Neuhauser: _Polynomization of the Bessenrodt–Ono type inequalities for $A$-partition functions._ Ann. Comb. (2024). https://doi.org/10.1007/s00026-024-00692-4
  * [GMU24] K. Gajdzica, P. Miska, M. Ulas: _On a general approach to Bessenrodt–Ono type inequalities and log-concavity properties._ Ann. Comb. (2024). https://doi.org/10.1007/s00026-024-00700-7
  * [GORZ19] M. Griffin, K. Ono, L. Rolen, D. Zagier: _Jensen polynomials for the Riemann zeta function and other sequences._ Proc. Natl. Acad. Sci., USA 116 No. 23 (2019), 11103–11110.
  * [Ha71] P. Hagis: _Partitions with a restriction on the multiplicity of the summands._ Trans. Amer. Math. Soc. 155 (1971), 375–384.
  * [HN19] B. Heim, M. Neuhauser: _Variants of a partition inequality of Bessenrodt–Ono._ Research in Number Theory 5 Article #32 (2019).
  * [HN22] B. Heim, M. Neuhauser: _Proof of the Bessenrodt–Ono inequality by induction._ Research in Number Theory 8 Article #3 (2022).
  * [HNT20] B. Heim, M. Neuhauser, R. Tröger: _Polynomization of the Bessenrodt–Ono inequality._ Ann. Comb. 24 (2020), 697–709.
  * [HNT23] B. Heim, M. Neuhauser, R. Tröger: Inequalities for plane partitions. Ann. Comb. 27 (2023), 87–108.
  * [HJ18] E. Hou, M. Jagadeesan: _Dyson’s partition ranks and their multiplicative extension._ Ramanujan J. 45 No. 3 (2018), 817–839.
  * [Le39] D. H. Lehmer: _On the remainders and convergence of the series for the partition functions._ Trans. Amer. Math. Soc. 46 (1939), 362–373.
  * [Li23] X. Li: _Polynomization of the Liu–Zhang inequality for the overpartition function._ Ramanujan J. 62 (2023), 797–817.
  * [Ma20] J. Males: _Asymptotic equidistribution and convexity for partition ranks._ Ramanujan J. 54 No. 2 (2021), 397–413.
  * [Ni78] J.-L. Nicolas: _Sur les entiers $N$ pour lesquels il y a beaucoup des groupes abéliens d’ordre $N$._ Ann. Inst. Fourier 28 No. 4 (1978), 1–16.
  * [On04] K. Ono: The Web of Modularity: Arithmetic of the Coefficients of Modular Forms and q-series. CBMS Regional Conference Series in Mathematics 102, American Mathematical Society, Providence, RI (2004).
  * [Ra37] H. Rademacher: _A convergent series for the partition function $p(n)$._ Proc. Natl. Acad. Sci. USA 23 (1937), 78–84.


# Predicting cross-linguistic adjective order with information gain

William Dyer
Oracle Corporation
<EMAIL_ADDRESS>
&Richard Futrell
University of California, Irvine
<EMAIL_ADDRESS>
Zoey Liu
Boston College
<EMAIL_ADDRESS>
&Gregory Scontras
University of California, Irvine
<EMAIL_ADDRESS>
###### Abstract

Languages vary in their placement of multiple adjectives before, after, or
surrounding the noun, but they typically exhibit strong intra-language
tendencies on the relative order of those adjectives (e.g., the preference for
‘big blue box’ in English, ‘grande boîte bleue’ in French, and ‘alṣundūq
al’azraq alkabīr’ in Arabic). We advance a new quantitative account of
adjective order across typologically-distinct languages based on maximizing
information gain. Our model addresses the left-right asymmetry of French-type
ANA sequences with the same approach as AAN and NAA orderings, without appeal
to other mechanisms. We find that, across 32 languages, the preferred order of
adjectives largely mirrors an efficient algorithm of maximizing information
gain.

##  1 Introduction

Languages that allow multiple sequential adjective modifiers tend to exhibit
strong tendencies on the relative order of adjectives, as in ‘big blue box’
vs. ‘blue big box’ in English (Dixon, 1982). To date, most of the research on
adjective ordering has focused on preferences in pre-nominal languages like
English where adjectives precede the modified noun (Futrell et al., 2020a), or
in post-nominal languages like Arabic where adjectives follow the noun
(Kachakeche and Scontras, 2020). This research usually posits a metric, such
as information locality (Futrell et al., 2020b) or subjectivity (Scontras et
al., 2017), which governs the preferred distance between a noun and its
adjectives. Because these theories predict only the relative linear _distance_
between noun and adjective, they cannot be straightforwardly applied to mixed
languages like French, where adjectives regularly appear both before and after
the modified noun, at least not without added assumptions about hierarchical
distance (Cinque, 1994). Instead, these mixed languages are often modeled with
constraints on which adjective classes or functions can appear before or after
a noun (Cinque, 2010; Fox and Thuilier, 2012).

Traditional accounts of adjective ordering in the linguistics literature often
assume a tree structure in which the target measure is the hierarchical
distance from noun (N) to adjective (A). According to syntactic accounts,
ordering regularities are predicted by a universal hierarchy of lexical
semantic classes (e.g., color adjectives are hierarchically closer to the
modified noun than size adjectives; Cinque, 1994; Scott, 2002). Alternative
accounts use aspects of adjective meaning to predict adjective order, making
appeal to notions like ‘inherentness’ (Whorf, 1945) or ‘definiteness of
denotation’ (Martin, 1969). Recently, Scontras et al. (2017) provide
experimental evidence that their synthesis of semantic predictors into a
continuum based on subjectivity reliably predicts ordering preference in
English; followup studies have found subjectivity to be a reliable predictor
in other languages as well (Tagalog: Samonte and Scontras, 2019; Mandarin: Shi
and Scontras, 2020; Arabic: Kachakeche and Scontras, 2020; Spanish: Jr. and
Scontras, 2019; Scontras et al., 2020). Explanations for the role of
subjectivity in adjective ordering show how subjectivity-based orderings are
more efficient than alternative orderings, thereby maximizing communicative
success (Simonič, 2018; Hahn et al., 2018; Franke et al., 2019; Scontras et
al., 2019).

Other efficiency-based approaches to adjective order quantify efficiency with
information-theoretic measures of word distributions such as surprisal or
entropy (Cover and Thomas, 2006; Levy, 2008). Models in this vein have a long
conceptual history in the field, originating with the idea that semantic
closeness between words is reflected in syntactic closeness in a surface
realization (Sweet, 1900; Jespersen, 1922; Behaghel, 1932). Modern
quantitative incarnations include integration cost (Dyer, 2017) and
information locality (Futrell et al., 2020b), both generalizations of the
widely-accepted principle of dependency distance minimization (Liu et al.,
2017; Temperley and Gildea, 2018).

Crucially, while previous approaches are able to model symmetrical structures
within the noun phrase, as in the mirror-image $A_{1}A_{2}N$ orders of English
and the $NA_{2}A_{1}$ orders of Arabic, a hierarchical approach cannot model
the left–right asymmetry of Romance $A_{1}NA_{2}$ without an appeal to other
mechanisms.

We advance an information-theoretic factor that predicts adjective ordering
across the three typological ‘templates’ of adjective order—pre (AAN), mixed
(ANA), and post (NAA)—based on information gain (IG), a measure of the
reduction in uncertainty attained by transforming a dataset. IG is used in
machine learning for ordering the nodes of a decision tree Quinlan (1986);
Norouzi et al. (2015), where nodes are most often ordered in a greedy fashion
such that the information gain of each node is maximized. By analogy, we view
the noun phrase as a decision tree for reducing a listener’s uncertainty about
a speaker’s intended meaning. Each word acts as a node in the decision tree;
preferred adjective orders thus reflect an efficient ordering of nodes.

##  2 Empirical background

Empirical investigations of adjective ordering have focused on the cross-
linguistic stability of these preferences across a host of unrelated languages
(e.g., Dixon, 1982; Hetzron, 1978; Sproat and Shih, 1991). For example, where
English speakers prefer ‘big blue box’ to ‘blue big box’, Mandarin speakers
similarly prefer _dà-de lán-de xiāng-zi_ ‘big blue box’ to _lán-de dà-de
xiāng-zi_ ‘blue big box’ (Shi and Scontras, 2020). In post-nominal languages,
we find the mirror-image of the English pattern, such that adjectives that are
preferred closer to the noun in pre-nominal languages are also preferred
closer to the noun in post-nominal languages.111Celtic languages have been
claimed to be an exception to this trend (Sproat and Shih, 1991), though our
own investigations into Irish suggest that it behaves like other post-nominal
languages, at least with respect to information gain. For example, speakers of
Arabic prefer _alṣundūq al’azraq alkabīr_ ‘the box blue big’ to _alṣundūq
alkabīr al’azraq_ ‘the box big blue’.

In support of the cross-linguistic stability of adjective ordering
preferences, Leung et al. (2020) present a latent-variable model capable of
accurately predicting adjective order in 24 languages from seven different
language families, achieving a mean accuracy of 78.9% on an average of 1335
sequences per language. Importantly, the model succeeds even when the training
and testing languages are different, thus demonstrating that different
languages rely on similar preferences. However, Leung et al.’s study was
limited to AAN and NAA templates. There has been very little corpus-based
empirical work on ordering preferences in the mixed ANA template, where
adjectives both precede and follow the modified noun.222We note two studies
that have examined adjective orders in five Romance languages from a
quantitative perspective: Gulordava et al. (2015) and Gulordava and Merlo
(2015). Different from our work, their studies looked at noun phrases with
only one adjective phrase dependent.

While Leung et al. (2020) learn adjective order by training on observed
adjective pairs, an alternate strategy is to posit one or more a priori
metrics as an underlying motivation for adjective order (e.g., Malouf, 2000,
in part). This approach allows for the study of why adjective orders might
have come about. To that end, Futrell et al. (2020a) report an accuracy of
72.3% for English triples based on a combination of subjectivity and
information-theoretic measures derived from the distribution of adjectives and
nouns.

To our knowledge, the current study is the first attempt at predicting
adjective order across all three templates, with an eye not only to raw
accuracy, but in hopes of illuminating the functional pressures which might
contribute to word ordering preferences in general.

##  3 Information gain

###  3.1 Picture of communication

We assume that a speaker is trying to communicate a meaning to a listener,
with a meaning represented as a binary vector, where each dimension of the
vector corresponds to a feature. Multiple features can be true simultaneously.
For example, a speaker might have in mind a vector like $m_{1}=[111\ldots 0]$
in Figure 1, where the vector has value 1 in the dimensions for ‘is-big’
($f_{0}$), ‘is-grey’ ($f_{1}$), and ‘is-elephant’ ($f_{2}$), and 0 for all
other features. A meaning of this sort would be conveyed by the noun phrase
‘big grey elephant’. We call $m$ a feature vector and the set of feature
vectors $M$.

The listener does not know which meaning $m$ the speaker has in mind; the
listener’s state of uncertainty can be represented as a probability
distribution over all possible feature vectors, $P(m)$, corresponding to the
prior probability of encountering a given feature vector. We call this
distribution the listener distribution $L$.

By conveying information, each word in a sequence causes a change in the
listener’s prior distribution. Suppose as in Figure 1 that a listener starts
with probability distribution $L$, then hears a word $w$ conveying a feature
($f_{2}$), resulting in the new distribution $L^{\prime}$. The amount of
change from $L$ to $L^{\prime}$ is properly measured using the
Kullback–Leibler (KL) divergence $D_{\text{KL}}[L^{\prime}||L]$ (Cover and
Thomas, 2006). Therefore, the divergence $D_{\text{KL}}[L^{\prime}||L]$
measures the amount of information about meaning conveyed by the word.

Another measure of the change induced by a word is the information gain, an
extension of KL divergence to include the notion of negative evidence. Let
$\bar{L^{\prime}}$ represent the listener’s probability distribution over
feature vectors conditional on the negation of $w$. By taking a weighted sum
of the positive and negative KL divergence, we recover information gain
(Quinlan, 1986):

$\text{IG}=\frac{|L^{\prime}|}{|L|}D_{\text{KL}}[L^{\prime}||L]+\frac{|\bar{L}^{\prime}|}{|L|}D_{\text{KL}}[\bar{L^{\prime}}||L],$
(1)

where $|L|$ indicates the number of elements in the support of $L$ with non-
zero probability. Information gain represents the information conveyed by a
word and also the information conveyed by its negation.

1 1 0 10 1 1 10 1 1 0⋮⋮⋮⋮1 0 1 0$\left[\vbox{\hrule
height=37.5869pt,depth=37.5869pt,width=0.0pt}\right.$$\left.\vbox{\hrule
height=37.5869pt,depth=37.5869pt,width=0.0pt}\right]$$f_{0}$ $f_{1}$ $f_{2}$
$\vdots$ $f_{k}$ $m_{0}$$m_{1}$$m_{2}$$m_{3}$$M$:$m_{0}$ $m_{1}$ $m_{2}$
$m_{3}$0.1 0.3 0.2 0.4$L$:$m_{0}$ $m_{1}$ $m_{2}$ $m_{3}$0.0 0.6 0.4
0.0$L^{\prime}$:$m_{0}$ $m_{1}$ $m_{2}$ $m_{3}$0.2 0.0 0.0
0.8$\bar{L^{\prime}}$:$w$$f_{2}$$\bar{f_{2}}$ Figure 1: A toy universe
composed of four feature vectors $m$ defined by $k$ binary features $f$ and an
associated probability distribution $L$. Partitioning $L$ on $f_{2}$ yields
$L^{\prime}$, the probability distribution of the feature vectors containing a
1 for $f_{2}$, viz. $m_{1}$ and $m_{2}$, as well as $\bar{L^{\prime}}$, the
distribution of feature vectors containing a 0 for $f_{2}$, or $\bar{f_{2}}$.

Below, we discuss how information gain relates to other information-theoretic
quantities, and why it is useful for us for predicting adjective order across
typological templates.

###  3.2 Relationship to other quantities

Our IG quantity in Eq. 1 is drawn from the ID3 algorithm for generating
decision trees (Quinlan, 1986). The goal of ID3 is to produce a classifier for
some random variable (call it $L$) which works by successively evaluating some
set of binary features in some order. The optimal order of these features is
given by greedily maximizing information gain, where information gain for a
feature $f$ is a measure of how much the entropy of $L$ is decreased by
partitioning the dataset into positive and negative subsets based on whether
$f$ is present or absent. Our application of information gain to word order
comes from treating each word as a binary indicator for the presence or
absence of the associated feature, and then applying the ID3 algorithm to
determine the optimal order of these features.

The first term of Eq. 1, the divergence $D_{\text{KL}}[L^{\prime}||L]$,
measures the amount of information about $L$ conveyed by the word $w$ and has
been the subject of a great deal of study in psycholinguistics. In particular,
Levy (2008) shows that if the word $w$ and the context $c$ can be
reconstructed perfectly from the updated belief state $L^{\prime}$, then the
amount of information conveyed by $w$ reduces to nothing other than the
surprisal of word $w$ in context $c$:

$D_{\text{KL}}[L^{\prime}||L]=-\log p(w|c).$ (2)

Importantly for our purposes, the positive evidence term
$D_{\text{KL}}[L^{\prime}||L]$ alone is unlikely to make useful predictions
about cross-linguistic word-order preferences, because surprisal is invariant
to reversal of word order across a language as a whole (Levy, 2005; Futrell,
2019): the same surprisal values would be measured for any given language and
a language with all the same sentences in reverse order. Therefore, these
metrics are unable to predict any a priori asymmetries in word-order
preferences between pre- and post-nominal positions.

###  3.3 Negative evidence

The new feature of information gain, which has not been presented in previous
information-theoretic models of language, is the negative evidence term in
$D_{\text{KL}}[\bar{L}^{\prime}||L]$, indicating the change in the listener’s
belief about $L$ given the negation of the features indicated by word $w$, a
quantity related to extropy Lad et al. (2015). For example, consider _académie
militaire_ ‘military academy’ in French. Let $L$ represent a listener’s belief
state after having heard the noun académie ‘academy’. Upon hearing the
adjective militaire ‘military’, $L$ is partitioned into $L^{\prime}$—the
portion of $L$ in which militaire is a feature—and $\bar{L^{\prime}}$, the
portion of $L$ in which militaire is not a feature. Put another way,
$\bar{L^{\prime}}$ is the probability distribution over non-military
academies.

The negative evidence portion of information gain is of primary interest to us
because it breaks the symmetry to word-order reversal that we would have if we
used the positive evidence term alone. Therefore, information gain can predict
left–right asymmetrical word-order preferences such as the order of adjectives
in ANA templates; it also maps onto a well-known decision rule for the
ordering of trees.

##  4 Methodology

###  4.1 Data

Our study relies on two types of source data, both extracted from the CoNLL
2017 Shared Task: Multilingual Parsing from Raw Text to Universal Dependencies
(Ginter et al., 2017; Zeman et al., 2017) a set of Common Crawl and Wikipedia
text data across a variety of languages, automatically parsed according to the
Universal Dependencies scheme with UDPipe (Straka and Straková, 2017). First,
we extract noun phrases (NPs) containing at least one adjective as the source
of feature vectors (§4.3). Second, we extract triples, instances of a noun and
two dependent adjectives in any order, where the three words are sequential in
the surface order and neither the noun nor the adjectives have any other
dependents.

We restrict triples in this way to minimize the effect that other dependents
might have on order preferences. For example, while single-word adjectives
tend to precede the noun in English, as in ‘the nice people’, adjectives in
larger right-branching phrases often follow: ‘the people nice to us’
(Matthews, 2014), a trend also seen in Romance (Gulordava et al., 2015;
Gulordava and Merlo, 2015). Similarly, conjunctions have been shown to weaken
or neutralize preferences (Fox and Thuilier, 2012; Jr. and Scontras, 2019;
Scontras et al., 2020).

NPs and triples extracted from the Wikipedia dumps are used to generate
feature vectors and to train our regression (§4.4). We use triples from the
Common Crawl dumps to perform hold-out accuracy testing.

###  4.2 Normalization

Because our source data are extracted from dumps of automatically-parsed text,
they contain a large amount of noise, such as incorrectly assigned syntactic
categories, HTML, nonstandard orthography, and so on. To combat this noise, we
extract all lemmas marked as ADJ and NOUN in all Universal Dependencies (UD)
v2.7 corpora (Zeman et al., 2020) for a given language—the idea being that the
UD corpora are of higher quality—and include only NPs and triples in which the
adjectives and nouns are in the UD lists. All characters are case-normalized,
where applicable.

###  4.3 Feature vectors

Each NP attested in the Wikipedia corpus for a given language corresponds to a
feature vector with value 1 in the dimension associated with each adjective or
noun lemma. For example, an NP such as “the best room available” generates a
vector containing 1 for ‘is-available’, ‘is-best’, and ‘is-room’.

The relative count of each NP in the Wikipedia corpus yields a probability
distribution on feature vectors. It is this distribution which is transformed
by partitioning on each lemma in a triple.

$-10$$0$$10$$20$$30$$40$$50$$60$$70$$0.4$$0.6$$0.8$$1$bgcsdadeelenfihrlvnlruskslsvtrukurzhcaeseufafrglhriditplptroviarcaeseufafrglheiditptrovi$\beta_{1}$accuracyAANANANAA
Figure 2: Plot of accuracy and $\beta_{1}$ coefficient, categorized by
template type.

###  4.4 Evaluation

For a given typological template (AAN, ANA, or NAA) there are two competing
variants; our tasks are to (i) predict which of the variants will be attested
in a corpus and (ii) show a cross-linguistic consistency in how that
prediction comes about.

Because we are limiting our study to the two competing variants within each
template, the position of the noun is invariant, leaving only the relative
order of the two adjectives to determine the order of a triple. Our problem
thus reduces to whether the information gain of the first linear adjective is
greater than that of the second.

In the case of AAN and ANA triples, the IG of each adjective is calculated by
partitioning the entire set of feature vectors $L$ on each of the two
adjectives. In the case of NAA triples, however, IG is calculated by
partitioning only those feature vectors which ‘survive’ the initial partition
by the noun, and are therefore part of $L^{\prime}$. Thus we calculate
$\text{IG}(L,a)$ before the noun and $\text{IG}(L^{\prime},a)$ after.

Rather than simply implement the ID3 algorithm and choose adjectives based on
their raw information gain, we train a logistic regression to predict surface
orders based on the _difference_ of IG between the attested first and second
adjective, a method previously used by Morgan and Levy (2016) and Futrell et
al. (2020a). The benefits of this approach are two-fold: we are able to
account for bias in the distribution of adjectival IGs, and we can more easily
deconstruct how strong information gain is as a predictor of adjective order.

Within each template, for each attested triple $\tau$, let $\pi_{1}$ be the
lexicographically-sorted first permutation of $\tau$ and $\pi_{2}$ be the
second, with $\alpha_{1}$ being the first linear adjective in $\pi_{1}$ and
$\alpha_{2}$ being the first linear adjective in $\pi_{2}$. Our independent
variable $p$ is whether $\pi_{1}$ is attested in the corpus, and our dependent
variable is the difference between the information gain of $\alpha_{1}$ and
$\alpha_{2}$. We train the coefficients $\beta_{0}$ and $\beta_{1}$ in a
logistic regression of the form

$\begin{split}p&=\begin{cases}1,&\text{if}\ \pi_{1}\text{ is attested}\\\
0,&\text{if}\ \pi_{2}\text{ is attested}\\\ \end{cases}\\\
\log\frac{p}{1-p}&\sim\beta_{0}+\beta_{1}[\text{IG}(\alpha_{1})-\text{IG}(\alpha_{2})].\end{split}$
(3)

A positive value for $\beta_{1}$ tells us that permutations in which the
larger-IG adjective is placed first tend to be attested. The value of
$\beta_{0}$ tells us whether there is a generalized bias towards a positive or
negative $\text{IG}(\pi_{1})-\text{IG}(\pi_{2})$. The accuracy we achieve by
running the logistic regression on held-out testing data tells us the
effectiveness of an IG-based algorithm at predicting adjective order.

###  4.5 Reporting results

We report results for languages from which at least 5k triples could be
analyzed, and for templates representing at least 10% of a language’s triples
in UD corpora. The count of analyzable triples for each language is a product
of those available in the 2017 CoNLL Shared Task, those with sufficiently
large UD v2.7 corpora, and those that meet our extraction requirements (§4.1).

Because we are interested in exploring a cross-linguistic predictor of
adjective order, we report macro-average accuracies and $\beta_{1}$
coefficients. That is, each language’s accuracy and coefficient are calculated
independently and are then averaged. We report both type- and token-accuracy,
using the latter in our analysis based on the intuition that the preference
for the order of a commonly-occurring triple is stronger than a more rare one.

##  5 Results

We extracted and analyzed at least 5k triples from 32 languages across a
variety of families. Because some languages contain triples in two typological
templates, we report results for 44 sets of triples. Table 1 reports language-
specific results and means for each template, including $n$ triples analyzed,
regression coefficient $\beta_{1}$ and $P$-value, token and type accuracy, and
95% confidence intervals. Figure 2 shows a plot of accuracy and $\beta_{1}$
coefficient for each language, categorized by template.

AAN | language | $n$ | $\beta_{1}$ | $P$ | token acc. | type acc.
---|---|---|---|---|---|---
mean $\beta_{1}$ | Bulgarian | 13018 | 20.058 | 0.000 | 0.650 | 0.649
18.591 [15.740, 21.443] | Chinese | 5909 | 18.604 | 0.000 | 0.724 | 0.766
| Croatian | 15555 | 21.246 | 0.000 | 0.666 | 0.634
mean token accuracy | Czech | 27899 | 28.207 | 0.000 | 0.671 | 0.665
0.656 [0.630, 0.683] | Danish | 11226 | 17.506 | 0.000 | 0.786 | 0.770
| Dutch | 11279 | 12.201 | 0.000 | 0.609 | 0.605
mean type accuracy | English | 23311 | 22.076 | 0.000 | 0.643 | 0.647
0.645 [0.616, 0.674] | Finnish | 12605 | 15.342 | 0.000 | 0.655 | 0.644
| German | 16391 | 16.210 | 0.000 | 0.601 | 0.606
| Greek | 5506 | 18.383 | 0.000 | 0.631 | 0.643
| Latvian | 5290 | 15.826 | 0.000 | 0.594 | 0.551
| Russian | 25397 | 25.697 | 0.000 | 0.658 | 0.651
| Slovak | 11933 | 25.935 | 0.000 | 0.700 | 0.651
| Slovenian | 18859 | 28.192 | 0.000 | 0.670 | 0.661
| Swedish | 10937 | 11.462 | 0.000 | 0.717 | 0.711
| Turkish | 12115 | 12.579 | 0.000 | 0.576 | 0.577
| Ukrainian | 11474 | 15.949 | 0.000 | 0.593 | 0.592
| Urdu | 6432 | 9.170 | 0.000 | 0.673 | 0.593
ANA | language | $n$ | $\beta_{1}$ | $P$ | token acc. | type acc.
mean $\beta_{1}$ | Basque | 3322 | -9.623 | 0.000 | 0.703 | 0.678
31.313 [16.786, 45.841] | Catalan | 3117 | 45.135 | 0.000 | 0.818 | 0.814
| Croatian | 4912 | -3.411 | 0.106 | 0.608 | 0.604
mean token accuracy | French | 5673 | 43.349 | 0.000 | 0.771 | 0.756
0.737 [0.674, 0.799] | Galician | 5020 | 68.290 | 0.000 | 0.805 | 0.806
| Indonesian | 1521 | -2.462 | 0.138 | 0.543 | 0.524
mean type accuracy | Italian | 9484 | 36.658 | 0.000 | 0.681 | 0.698
0.726 [0.665, 0.787] | Persian | 2598 | 43.242 | 0.000 | 0.794 | 0.766
| Polish | 13481 | 24.873 | 0.000 | 0.684 | 0.655
| Portuguese | 7580 | 32.374 | 0.000 | 0.734 | 0.725
| Romanian | 2426 | 46.823 | 0.000 | 0.730 | 0.739
| Spanish | 9212 | 57.813 | 0.000 | 0.744 | 0.738
| Vietnamese | 2636 | 24.013 | 0.000 | 0.962 | 0.931
NAA | language | $n$ | $\beta_{1}$ | $P$ | token acc. | type acc.
mean $\beta_{1}$ | Arabic | 11595 | 4.595 | 0.000 | 0.693 | 0.660
4.140 [3.128, 5.152] | Basque | 4899 | 1.957 | 0.000 | 0.626 | 0.635
| Catalan | 2878 | 5.024 | 0.000 | 0.710 | 0.722
mean token accuracy | French | 8368 | 5.143 | 0.000 | 0.737 | 0.749
0.680 [0.639, 0.721] | Galician | 1334 | 5.776 | 0.000 | 0.716 | 0.694
| Hebrew | 6751 | 1.115 | 0.000 | 0.558 | 0.560
mean type accuracy | Indonesian | 5724 | 4.631 | 0.000 | 0.740 | 0.734
0.687 [0.647, 0.726] | Italian | 4523 | 4.057 | 0.000 | 0.713 | 0.739
| Persian | 12683 | 1.583 | 0.000 | 0.605 | 0.606
| Portuguese | 5139 | 5.329 | 0.000 | 0.726 | 0.730
| Romanian | 8492 | 5.333 | 0.000 | 0.742 | 0.746
| Spanish | 6245 | 6.214 | 0.000 | 0.713 | 0.745
| Vietnamese | 3354 | 3.068 | 0.000 | 0.561 | 0.606
| comprehensive mean | 18.08 |  | 0.687 | 0.681
Table 1: Results by template and language: $n$ triples analyzed, regression
coefficient $\beta_{1}$ and $P$-value, and test accuracies. Means with 95%
confidence intervals shown for each template.

As reported in Table 1, we find above-chance $(>50\%)$ accuracy for all
languages tested. We accurately predict 65.6% of AAN triples, 73.7% of ANA
triples, and 68.0% of NAA triples, for a comprehensive accuracy across all
languages of 68.7%. Overlapping 95% confidence intervals across template means
suggest that IG-based prediction performs equally well across templates.

Though we cannot make a direct comparison to other studies due to a lack of
standardized datasets, our cross-linguistic accuracy of 68.4% based on a
single predictor compares reasonably favorably to a previous analysis of
English AAN triples which achieved 72.3% accuracy using a combination of
predictors (Futrell et al., 2020a).

The high performance on Vietnamese ANA triples (96.2%) is largely due to the
algorithm correctly predicting that the highly-frequent adjective nhiều ‘many’
should be placed before the noun, while most other adjectives are placed
after.333One might worry about the classification of ‘many’ as an adjective.
While widely extant across languages, the class of adjectives is not entirely
homogeneous. As such, the equivalent of a word like ‘many’ in some languages
might be marked as an adjective, determiner, or other syntactic category. For
the current study, we simply follow the UD annotation scheme.

The learned $\beta_{1}$ coefficient is not significantly different between AAN
(18.591) and NAA (31.313) triples, though that of NAA (4.140) triples is
significantly smaller than the other two. More generally, of the 44 datasets
tested, $\beta_{1}$ is positive in 41 (93.2%), suggesting that there is a
strong preference to maximize information gain. Further, of the three
instances of a negative $\beta_{1}$, two (Croatian and Indonesian ANA) do not
reach significance, perhaps due to a paucity of data. The sole significant
negative $\beta_{1}$ is from Basque ANA triples.

##  6 Discussion

###  6.1 Asymmetries

The preference for one variant of an ANA triple over the other is an asymmetry
without a straightforward explanation in a distance-based model; there is no
clear mapping from ANA onto the other templates, which means that an
adjective’s relative distance to the noun is not informative. Our algorithm is
novel in that the placement of the adjectives is governed by greedy IG, not
distance to the noun—an innovation that allows us to break the symmetry
between the adjectives in ANA triples. Similarly, IG makes no a priori
prediction as to whether a mirror- or same-order will emerge between AAN and
NAA triples: both pre- and post-nominal behavior is a product of ordering
adjectives such that information gain is maximized, and IG itself is
fundamentally derived from the distribution of adjectives and nouns that
populate a language’s possible feature vectors for conveying meaning.

Another left–right asymmetry that has been posited in the linguistics
literature holds that dependents placed before the head in a surface
realization (e.g., the adjectives in an AAN triple) follow a more rigid
ordering than those placed after (e.g., the adjectives in a NAA triple;
Hawkins, 1983). Both noun modifiers in general and adjectives specifically
have been reported to follow this pattern, with a largely-universal pre-
nominal ordering and a mirror, same, or ‘free’ post-nominal order (Hetzron,
1978). However, there is as yet no large-scale empirical evidence for this
claim.

In an effort to empirically assess the claim that post-nominal orderings are
more flexible compared to orderings pre-nominally, Table 2 reports the average
prevalence of adjective pairs attested in both possible orders (e.g., A1A2N
and A2A1N, where N can be any noun) within each template in our dataset. At
95% confidence the difference between AAN and NAA does not reach significance,
though the rate for ANA is significantly lower than the other two. More
generally, the mean rate of just 1.6% across templates reinforces the notion
that ordering preferences are quite robust regardless of template, at least
for our normalized triples from the languages analyzed here.

| $n$ | rate | confidence interval
---|---|---|---
AAN | 18 | 0.017 | [0.012, 0.022]
ANA | 13 | 0.007 | [0.002, 0.011]
NAA | 13 | 0.022 | [0.013, 0.032]
all | 44 | 0.016 | [0.012, 0.020]
Table 2: Macro-average rate of adjectives attested in both orders by template,
showing $n$ languages, rate, and 95% confidence intervals.

###  6.2 Ablation

Equation 1 defines information gain as the conditioned sum of two elements,
the positive evidence $D_{\text{KL}}[L^{\prime}||L]$ and the negative evidence
$D_{\text{KL}}[\bar{L^{\prime}}||L]$. The positive evidence alone is akin to
surprisal, a well-studied quantity in psycholinguistics (§3.2). By ablating
the IG formulation into the two terms discretely, we can show empirically that
the proportionally-combined positive and negative evidence yield more accurate
and consistent results than either of the two constituent terms alone.

| accuracy | proportion of positive $\beta_{1}$
---|---|---
| AAN | ANA | NAA | all | AAN | ANA | NAA | all
$D_{\text{KL}}[L^{\prime}||L]$ | 0.565 | 0.567 | 0.565 | 0.566 | 0.000 | 0.154 | 0.769 | 0.273
$D_{\text{KL}}[\bar{L^{\prime}}||L]$ | 0.533 | 0.548 | 0.526 | 0.535 | 0.167 | 0.231 | 0.462 | 0.273
IG | 0.657 | 0.737 | 0.680 | 0.687 | 1.000 | 0.769 | 1.000 | 0.932
Table 3: Ablation on accuracy and the proportion of positive coefficients for
positive evidence ($D_{\text{KL}}[L^{\prime}||L]$), negative evidence
($D_{\text{KL}}[\bar{L^{\prime}}||L]$), and proportionally combined (IG).
Boldfaced values indicate the highest accuracy or coefficient polarity
proportion in each column.

Table 3 shows the mean accuracy and polarity proportion of the $\beta_{1}$
coefficient across languages and templates. The polarity of $\beta_{1}$ tells
us whether maximizing IG (positive) or minimizing IG (negative) is the better
strategy. Thus a polarity percentage close to 0 or 1 indicates more consistent
behavior across templates.

For example, while the accuracy of using only positive evidence,
$D_{\text{KL}}[L^{\prime}||L]$, is 0.565, that accuracy is realized due to a
0.000 rate of positive $\beta_{1}$ coefficient—that is, the 56.5% accuracy is
achieved by minimizing IG, placing the adjective with the lower IG first. On
the other hand, while using only positive evidence to predict NAA triples
yields the same accuracy, 0.565, the coefficient polarity proportion of 0.769
means that in most NAA cases IG should be maximized. The three templates
together reflect a modest accuracy (0.566) and an inconsistent coefficient
polarity proportion (0.273).

Using only negative evidence, $D_{\text{KL}}[\bar{L^{\prime}}||L]$, yields
even worse accuracies and similarly inconsistent coefficients as positive
only. Accuracy across templates is little better than chance at 0.535, and the
average coefficient polarity proportion of 0.273 likewise demonstrates that
using negative evidence alone does not produce consistent behavior across
templates.

The full IG calculation, including both positive and negative evidence, yields
the highest accuracy across templates (0.687), as well as the highest for each
template—AAN (0.657), ANA (0.737) and NAA (0.680). IG also demonstrates the
most consistent behavior across languages and templates: at a rate of 0.932,
maximizing IG yields the highest accuracy, regardless of whether adjectives
precede or follow the noun.

###  6.3 An efficient algorithm

The goal of algorithms such as ID3 is to produce a decision tree which divides
a dataset into equal-sized and mutually-exclusive partitions, thereby creating
a shallow tree (Quinlan, 1986). While finding the smallest possible binary
decision tree is NP-complete (Hyafil and Rivest, 1976), ID3’s locally-optimal
approach has proven quite effective at producing shallow trees capable of
accurate classification (Dobkin et al., 1996).

By analogy, the ordering of adjectives in a noun phrase by maximizing
information gain likewise produces a tree with balanced positive and negative
partitions at each node. Specifically, adjectives that minimize the entropy of
both the positive and negative evidence are placed before adjectives which are
less ‘decisive’ at partitioning feature vectors.

##  7 Summary

We have taken a novel approach to the problem of predicting the surface order
of adjectives across languages, casting it as a decision tree operating on a
probability distribution over binary feature vectors. As each adjective is
uttered, probability mass is partitioned into positive and negative subsets:
those vectors which contain the feature and those that do not. The information
gained by this partition can be used to order adjectives in a greedy manner,
similarly to well-known algorithms for ordering nodes in a decision tree.

An IG-based approach allows us to provide the first quantitative information-
theoretic account predicting the order of ANA triples. Further, with this
approach we need not stipulate mirror- or same-orders for AAN and NAA triples.
Because IG is not a distance metric between adjective and noun, and because IG
incorporates negative evidence, both ANA and pre- or post-nominal asymmetries
emerge within an IG framework, without appeal to other mechanisms.

Our results show that information gain is a good predictor of adjective order
across languages. Importantly, IG-based prediction follows a consistent
pattern across the three typological templates, namely that adjectives which
maximize information gain tend to be placed first.

## References

  * Behaghel (1932) Otto Behaghel. 1932.  _Deutsche Syntax eine geschichtliche Darstellung_ , volume IV.  Carl Winters Unversitätsbuchhandlung, Heidelberg.
  * Cinque (1994) Guglielmo Cinque. 1994.  On the Evidence for Partial N-Movement in the Romance DP.  In Guglielmo Cinque, Jan Koster, Jean-Yves Pollack, Luigi Rizzi, and Raffaella Zanuttini, editors, _Paths Towards Universal Grammar. Studies in Honor of Richard S. Kayne,_ , pages 85–110. Georgetown University Press, Washington, DC.
  * Cinque (2010) Guglielmo Cinque. 2010.  _The Syntax of Adjectives: A Comparative Study_.  The MIT Press, Camb., Mass.
  * Cover and Thomas (2006) Thomas M. Cover and Joy A. Thomas. 2006.  _Elements of Information Theory_.  John Wiley & Sons, Hoboken, NJ.
  * Dixon (1982) Robert M. W. Dixon. 1982.  _Where have all the adjectives gone? And other essays in semantics and syntax_.  Mouton, Berlin, Germany.
  * Dobkin et al. (1996) David Dobkin, Truxton Fulton, Dimitrios Gunopulos, Simon Kasif, and Steven Salzberg. 1996.  Induction of shallow decision trees.  _submitted to IEEE PAMI_.
  * Dyer (2017) William E. Dyer. 2017.  _Minimizing integration cost: A general theory of constituent order_.  Ph.D. thesis, University of California, Davis, Davis, CA.
  * Fox and Thuilier (2012) Gwendoline Fox and Juliette Thuilier. 2012.  Predicting the position of attributive adjectives in the french np.  In _New Directions in Logic, Language and Computation_ , pages 1–15. Springer.
  * Franke et al. (2019) Michael Franke, Gregory Scontras, and Mihael Simonič. 2019.  Subjectivity-based adjective ordering maximizes communicative success.  In _Proceedings of the 41st annual meeting of the Cognitive Science Society_ , pages 344–350.
  * Futrell (2019) Richard Futrell. 2019.  Information-theoretic locality properties of natural language.  In _Proceedings of the First Workshop on Quantitative Syntax (Quasy, SyntaxFest 2019)_ , pages 2–15, Paris, France. Association for Computational Linguistics.
  * Futrell et al. (2020a) Richard Futrell, William Dyer, and Gregory Scontras. 2020a.  What determines the order of adjectives in English? comparing efficiency-based theories using dependency treebanks.  In _Proc. of the 58th Annual Meeting of ACL_ , pages 2003–2012, Online. ACL.
  * Futrell et al. (2020b) Richard Futrell, Edward Gibson, and Roger P Levy. 2020b.  Lossy-context surprisal: An information-theoretic model of memory effects in sentence processing.  _Cognitive science_ , 44(3):e12814.
  * Ginter et al. (2017) Filip Ginter, Jan Hajič, Juhani Luotolahti, Milan Straka, and Daniel Zeman. 2017.  CoNLL 2017 shared task \- automatically annotated raw texts and word embeddings.  LINDAT/CLARIAH-CZ digital library at the Institute of Formal and Applied Linguistics (ÚFAL), Faculty of Mathematics and Physics, Charles University.
  * Gulordava and Merlo (2015) Kristina Gulordava and Paola Merlo. 2015.  Structural and lexical factors in adjective placement in complex noun phrases across Romance languages.  In _Proceedings of the Nineteenth Conference on Computational Natural Language Learning_ , pages 247–257, Beijing, China. Association for Computational Linguistics.
  * Gulordava et al. (2015) Kristina Gulordava, Paola Merlo, and Benoit Crabbé. 2015.  Dependency length minimisation effects in short spans: a large-scale analysis of adjective placement in complex noun phrases.  In _Proceedings of the 53rd Annual Meeting of the Association for Computational Linguistics and the 7th International Joint Conference on Natural Language Processing (Volume 2: Short Papers)_ , pages 477–482, Beijing, China. Association for Computational Linguistics.
  * Hahn et al. (2018) Michael Hahn, Judith Degen, Noah Goodman, Daniel Jurafsky, and Richard Futrell. 2018\.  An information-theoretic explanation of adjective ordering preferences.  In _Proceedings of the 40th Annual Meeting of the Cognitive Science Society_ , pages 1766–1772, Madison, WI. Cognitive Science Society.
  * Hawkins (1983) John A. Hawkins. 1983.  _Word Order Universals: Quantitative analyses of linguistic structure_.  New York: Academic Press.
  * Hetzron (1978) Robert Hetzron. 1978.  On the relative order of adjectives.  In Hansjakob Seiler, editor, _Language Universals_ , pages 165–184. Gunter Narr Verlag, Tübingen.
  * Hyafil and Rivest (1976) Laurent Hyafil and R Rivest. 1976.  Constructing optimal binary search trees is np complete.  _Information Processing Letters_.
  * Jespersen (1922) Otto Jespersen. 1922.  _Language: its nature and development_.  George Allen & Unwin Ltd., London.
  * Jr. and Scontras (2019) Cesar Manuel Rosales Jr. and Gregory Scontras. 2019.  On the role of conjunction in adjective ordering preferences.  _Proceedings of the Linguistic Society of America_ , 4(32):1–12.
  * Kachakeche and Scontras (2020) Zeinab Kachakeche and Gregory Scontras. 2020.  Adjective ordering in Arabic: Post-nominal structure and subjectivity-based preferences.  In _Proc. of the LSA_ , volume 5, pages 419–430.
  * Lad et al. (2015) Frank Lad, Giuseppe Sanfilippo, Gianna Agro, et al. 2015.  Extropy: complementary dual of entropy.  _Statistical Science_ , 30(1):40–58.
  * Leung et al. (2020) Jun Yen Leung, Guy Emerson, and Ryan Cotterell. 2020.  Investigating cross-linguistic adjective ordering tendencies with a latent-variable model.  In _Proceedings of the 2020 Conference on Empirical Methods in Natural Language Processing_.
  * Levy (2005) Roger Levy. 2005.  _Probabilistic Models of Word Order and Syntactic Discontinuity_.  Ph.D. thesis, Stanford University, Stanford, CA.
  * Levy (2008) Roger Levy. 2008.  Expectation-based syntactic comprehension.  _Cognition_ , 106(3):1126–1177.
  * Liu et al. (2017) Haitao Liu, Chunshan Xu, and Junying Liang. 2017.  Dependency distance: A new perspective on syntactic patterns in natural languages.  _Physics of Life Reviews_ , 21:171–93.
  * Malouf (2000) Robert Malouf. 2000.  The order of prenominal adjectives in natural language generation.  In _Proceedings of the 38th Annual Meeting of the Association for Computational Linguistics_ , pages 85–92.
  * Martin (1969) J. E. Martin. 1969.  Semantic determinants of preferred adjective order.  _Journal of Verbal Learning and Verbal Behavior_ , 8:697–704.
  * Matthews (2014) Peter Matthews. 2014.  _The Positions of Adjectives in English_.  Oxford University Press, New York.
  * Morgan and Levy (2016) Emily Morgan and Roger Levy. 2016.  Abstract knowledge versus direct experience in processing of binomial expressions.  _Cognition_ , 157:382–402.
  * Norouzi et al. (2015) Mohammad Norouzi, Maxwell D. Collins, Matthew Johnson, David J. Fleet, and Pushmeet Kohli. 2015.  Efficient non-greedy optimization of decision trees.  _arXiv:1511.04056 [cs]_.
  * Quinlan (1986) J. Ross Quinlan. 1986.  Induction of decision trees.  _Machine learning_ , 1(1):81–106.
  * Samonte and Scontras (2019) Suttera Samonte and Gregory Scontras. 2019.  Adjective ordering in Tagalog: A cross-linguistic comparison of subjectivity-based preferences.  In _Proceedings of the Linguistic Society of America_ , volume 4, pages 1–13.
  * Scontras et al. (2020) Gregory Scontras, Galia Bar-Sever, Zeinab Kachakeche, Cesar Manuel Rosales Jr., and Suttera Samonte. 2020.  Incremental semantic restriction and subjectivity-based adjective order- ing.  _Proceedings of Sinn und Bedeutung 24_ , pages 253–270.
  * Scontras et al. (2017) Gregory Scontras, Judith Degen, and Noah D. Goodman. 2017.  Subjectivity predicts adjective ordering preferences.  _Open Mind: Discoveries in Cognitive Science_ , 1(1):53–65.
  * Scontras et al. (2019) Gregory Scontras, Judith Degen, and Noah D. Goodman. 2019.  On the grammatical source of adjective ordering preferences.  _Semantics and Pragmatics_ , 12(7).
  * Scott (2002) Gary-John Scott. 2002.  Stacked adjectival modification and the structure of nominal phrases.  In _Functional Structure in DP and IP: The Cartography of Syntactic Structures_ , volume 1, pages 91–210. Oxford University Press, New York.
  * Shi and Scontras (2020) Yuxin Shi and Gregory Scontras. 2020.  Mandarin has subjectivity-based adjective ordering preferences in the presence of ‘de’.  In _Proceedings of the Linguistic Society of America_ , volume 5, pages 410–418.
  * Simonič (2018) Mihael Simonič. 2018.  Functional explanation of adjective ordering preferences using probabilistic programming.  Master’s thesis, University of Tübingen.
  * Sproat and Shih (1991) Richard Sproat and Chilin Shih. 1991.  The Cross-Linguistic Distribution of Adjective Ordering Restrictions.  In Carol Georgopoulos and Roberta Ishihara, editors, _Interdisciplinary Approaches to Language_ , pages 565 – 93. Kluwer Academic Publishers, Boston.
  * Straka and Straková (2017) Milan Straka and Jana Straková. 2017.  Tokenizing, POS Tagging, Lemmatizing and Parsing UD 2.0 with UDPipe.  In _Proc. of the CoNLL 2017 Shared Task: Multilingual Parsing from Raw Text to Universal Dependencies_ , pages 88–99, Vancouver. ACL.
  * Sweet (1900) Henry Sweet. 1900.  _A new English grammar, logical and historical_ , volume 1.  Clarendon Press, Oxford.
  * Temperley and Gildea (2018) David Temperley and Daniel Gildea. 2018.  Minimizing syntactic dependency lengths: Typological/cognitive universal?  _Annual Review of Linguistics_ , 4:1–15.
  * Whorf (1945) Benjamin Lee Whorf. 1945.  Grammatical Categories.  _Language_ , 21(1):1–11.
  * Zeman et al. (2020) Daniel Zeman, Joakim Nivre, … Abrams, and Anna Zhuravleva. 2020.  Universal dependencies 2.7.  LINDAT/CLARIAH-CZ digital library at the Institute of Formal and Applied Linguistics (ÚFAL), Faculty of Mathematics and Physics, Charles University.
  * Zeman et al. (2017) Daniel Zeman, Martin Popel, …, and Josie Li. 2017.  Multilingual parsing from raw text to universal dependencies.  In _Proc. of CoNLL 2017 Shared Task: Multilingual Parsing from Raw Text to Universal Dependencies_ , pages 1–19. ACL.