to herself a bundle of higher value (according to $v^{\prime}$) than the value
guaranteed (according to $v$) by reporting $v$. As $v>v^{\prime}$, this strict
inequality also holds when considering the value of bundles according to $v$
when the report is $v^{\prime}$. Formally: if $v,v^{\prime}\in{\mathcal{C}}$
such that $v\geq v^{\prime}$ but
$\hat{s}_{{v}}({{v}})<\hat{s}_{{v^{\prime}}}({{v^{\prime}}})$, then we get a
contradiction to $s$ being self maximizing. An agent with value
$v\in{\mathcal{C}}$ can increase her share guarantee by reporting
$v^{\prime}\in{\mathcal{C}}$ as
$\hat{s}_{{v}}({{v}})<\hat{s}_{{v^{\prime}}}({{v^{\prime}}})\leq\hat{s}_{{v}}({{v^{\prime}}})$,
where the second inequality follow from monotonicity ($v(S)\geq v^{\prime}(S)$
for any set $S$).

Suppose that $s$ is a share that is not $1$-Lipschitz for ${\mathcal{C}}$.
Then there is a value $\delta>0$ and two valuation functions,
$v,v^{\prime}\in{\mathcal{C}}$, such that for every bundle $S\in{\cal{M}}$ it
holds that $|v(S)-v^{\prime}(S)|\leq\delta$, but
$\hat{s}_{{v^{\prime}}}({{v^{\prime}}})=\hat{s}(v^{\prime},n)>\hat{s}(v,n)+\delta=\hat{s}_{{v}}({{v}})+\delta$.
Then $s$ is not self maximizing, because for an agent with valuation function
$v\in{\mathcal{C}}$, by reporting $v^{\prime}\in{\mathcal{C}}$ she guarantees
to herself a bundle of value (according to $v^{\prime}$) higher by more than
$\delta$ than the value guaranteed (according to $v$) by reporting $v$. As for
every bundle the values of $v^{\prime}$ and $v$ differ by at most $\delta$,
then when values are measured by respect to $v$, by reporting $v^{\prime}$ the
agent guarantees to herself a bundle of value strictly higher than the value
guaranteed by reporting $v$. Formally, if $|v(S)-v^{\prime}(S)|\leq\delta$ but
$\hat{s}_{{v^{\prime}}}({{v^{\prime}}})>\hat{s}_{{v}}({{v}})+\delta$ then
$\hat{s}_{{v}}({{v^{\prime}}})+\delta\geq\hat{s}_{{v^{\prime}}}({{v^{\prime}}})>\hat{s}_{{v}}({{v}})+\delta$,
and thus $\hat{s}_{{v}}({{v^{\prime}}})>\hat{s}_{{v}}({{v}})$, in
contradiction to the share being self maximizing for ${\mathcal{C}}$.
$\blacksquare$

###  E.2 Missing Proof from Section 3.3

####  E.2.1 Proof of Proposition 4

We restate and prove Proposition 4. See 4 Proof. The MMS dominates every
feasible share $s$ for ${\mathcal{C}}$, as if $s$ is strictly larger than the
MMS for some valuation $v$ in ${\mathcal{C}}$, it cannot be feasible because
the MMS is defined to be the largest value that can be concurrently given to
each of the $n$ agents when all have that valuation $v$. Thus, the MMS is a
dominant share for ${\mathcal{C}}$. If the MMS is also feasible for class
${\mathcal{C}}$, then it is a dominant feasible share (and thus also an SM-
dominant feasible share) for ${\mathcal{C}}$.

We next prove that when the MMS is feasible, it is the unique dominant
feasible share, and also the unique SM-dominant feasible share. Consider any
dominant feasible share $s$ for class ${\mathcal{C}}$. We have seen that the
MMS dominates $s$ (as $s$ is feasible), and as $s$ dominates the MMS (as $s$
is dominant and the MMS is feasible by assumption), $s$ must equal the MMS,
and thus the MMS is the unique dominant feasible share for ${\mathcal{C}}$.

As the MMS is self maximizing for any ${\mathcal{C}}$ (Proposition 2), if the
MMS is feasible, then every SM-dominant feasible share for ${\mathcal{C}}$
must dominate the MMS, and thus must equal the MMS. Thus, the MMS is the
unique SM-dominant feasible share for ${\mathcal{C}}$. $\blacksquare$

##  Appendix F Missing Proof from Section 4

###  F.1 Missing Proof from Section 4.1

####  F.1.1 Proof of Proposition 5

Proposition 5 directly follows from the following three lemmas.

When valuations are not additive, picking order shares need not be an ordinal
maximin share, but nevertheless, we show that they are self maximizing.

###### Lemma 14

Fix any class ${\mathcal{C}}$ of valuations. For any picking order $\omega$,
the $\omega$-Picking-Order share is self maximizing for ${\mathcal{C}}$.

Proof. Given a set ${\cal{M}}$ of items, a picking order $\omega$ and an
identity $i$ for the agent that has valuation $v_{i}$, consider the zero-sum
game with two players: the agent and the adversary. The agent gets to pick
items in her turns according to $\omega$, and the adversary picks items in the
remaining turns. The outcome of the game for the agent is the value (according
to $v_{i}$) of the bundle that she picked.

As the game is finite, there are only finitely many strategies for the
players. Every strategy $\sigma$ for the agent defines a collection of
feasible bundles, namely, those bundles for which there is some strategy of
the adversary that leads to the agent getting the bundle. The value of
strategy $\sigma$ for the agent is the smallest value of any of the respective
feasible bundles. The value of this zero-sum game is the highest value among
the values of the strategies of the agent, and is equal to the value of the
share.

Suppose that the agent reports a valuation function $v^{\prime}_{i}$ instead
of the true $v_{i}$. Then the implied guarantee with respect to
$v^{\prime}_{i}$ is determined by some specific strategy $\sigma^{\prime}$ in
the above game. All acceptable bundles with respect to $\sigma^{\prime}$ are
bundles that an agent with valuation function $v^{\prime}_{i}$ values at least
as much as her share (with respect to $v^{\prime}_{i}$), and hence might be
allocated to agent $i$ by an allocation algorithm that guarantees the share
value. Hence the value that this guarantees to agent $i$ is not larger than
the minimum value according to $v_{i}$ of a bundle that is acceptable for
$\sigma^{\prime}$. As $\sigma^{\prime}$ is among the strategies considered
when reporting $v_{i}$, and the share value for $v_{i}$ is computed according
to the best strategy, it follows that the implied guarantee when reporting the
true $v_{i}$ is at least as large as when reporting $v^{\prime}_{i}$.
$\blacksquare$

###### Lemma 15

Fix any class ${\mathcal{C}}$ of valuations. For any picking order $\omega$,
the $\omega$-Picking-Order share is feasible for ${\mathcal{C}}$. Moreover, if
valuations are additive then an acceptable allocation can be computed in
polynomial time.

Proof. Every agent simply follows the same strategy that defines her picking-
order share. Thus all agents simultaneously are guaranteed that each receives
an acceptable bundle. When an agent has an additive valuation, that strategy
simply picks a highest value available item at each picking point, thus the
allocation is poly-time computable. $\blacksquare$

Crucial to the proof of our main theorem is the next claim, showing that for
additive valuations, for some picking order the share is as large as the MMS.

###### Lemma 16

Consider a setting with $n$ agents and a set of items ${\cal{M}}$. For any
additive valuation $v$ there exists a picking order $\omega_{v}$ for which the
$\omega_{v}$-Picking-Order share for an agent with valuation $v$ equals to the
MMS of that agent, that is, to $MMS_{n}(v)$.

Proof. Consider any partition of the items to $n$ sets (parts) such that the
value of the lowest-value part equals to $MMS_{n}(v)$. For the given additive
valuation, order the items in non-increasing value order, breaking ties
arbitrarily. Name each item by its place in the order. Then define a picking
order $\omega_{v}$ using the MMS partition with each part associated with one
of the agents, and she gets to pick at the rounds that are defined by the
names of the items in that part. Every time an agent needs to pick, she picks
an available item that is of highest value, and due to additivity, she gets a
value at least as high as the value of her part. Thus the agent that gets the
lowest value gets at least her MMS (and no more, by the MMS definition).
$\blacksquare$

##  Appendix G Missing Proofs from Section 5.1

###  G.1 Proof of Theorem 2

See 2

Proof. All valuation functions throughout the proof are assumed to be from
class ${\mathcal{C}}$, and domination, feasibility and self-maximization of
shares is with respect to valuation function in class ${\mathcal{C}}$.

As $s$ is feasible, for every $m$ and $n$ there is an allocation algorithm
$A_{m,n}$ (though not necessarily a computationally efficient one) that for
every instance with $m$ items and $n$ agents provides an acceptable
allocation: one that gives every agent $i$ with valuation $v_{i}$ a bundle of
value at least $s(v_{i},n)$. Fix such an algorithm, $A_{m,n}$. Without loss of
generality, we shall assume that given the names of the agents and the items,
algorithm $A_{m,n}$ is deterministic. (For example, if $A_{m,n}$ was
randomized, we fix all its coin tosses in advance.) Algorithm $A_{m,n}$
partitions the valuation functions of ${\mathcal{C}}$ into at most $2^{2^{m}}$
sub-classes as follows. Each sub-class is represented by a binary vector
$x\in\\{0,1\\}^{2^{m}}$ of length $2^{m}$, where each entry in this vector is
indexed by a distinct bundle $B$ of items in ${\cal{M}}$. Given such a binary
vector $x$, valuation function $v$ belongs to the subclass associated with $x$
if and only if the following condition holds:

  * •

For every bundle $B\subset{\cal{M}}$, the corresponding entry $x_{B}$ in $x$
is 1 if and only if there is some setting of valuation functions for all
agents in which at least one agent (say agent $i$) has valuation function $v$,
and $A_{m,n}$ gives this agent $i$ the bundle $B$.

The collection of all subclasses is denoted by $\cal{S}$. For valuation
function $v$, we let $x^{v}$ denote the subclass that contains $v$.

For a valuation function $v$ and a subclass represented by $x$ (regardless if
$v$ belongs to this subclass or not), we define
$v(x)=\min_{\\{B\;|\;x_{B}=1\\}}[v(B)]$. We define the share $s^{\prime}$ as
$s^{\prime}(v,n)=\max_{x\in{\cal{S}}}[v(x)]$. Note that as $s^{\prime}$ is
defined to be a value of some bundle, its share guarantee $\hat{s}^{\prime}$
is the same as the share itself.

We need to show three properties for $s^{\prime}$.

  1. 1.

$s^{\prime}$ is feasible. This is established by the following allocation
algorithm $A^{\prime}_{m,n}$ (which is not necessarily computationally
efficient, not even if $A_{m,n}$ is computationally efficient). Given
valuation functions $v_{1},\ldots,v_{n}$, for every valuation function
$v_{i}$, algorithm $A^{\prime}_{m,n}$ determines the class $x$ that maximizes
$v_{i}(x)$ (breaking ties arbitrarily), and replaces $v_{i}$ by an arbitrary
valuation function $v^{\prime}_{i}$ from this class $x$ ($x$ is the class that
gives rise to the share value $s^{\prime}(v,n)$). Thereafter,
$A^{\prime}_{m,n}$ runs $A_{m,n}$ on inputs
$v^{\prime}_{1},\ldots,v^{\prime}_{n}$.

  2. 2.

$s^{\prime}$ is self maximizing. Suppose that one reports $v^{\prime}$ instead
of the true $v$. Then there is some subclass $z$ such that
$s^{\prime}(v^{\prime},n)=v^{\prime}(z)=\min_{\\{B\;|\;z_{B}=1\\}}[v^{\prime}(B)]$.
All bundles $B$ for which $z_{B}=1$ are acceptable bundles for $v^{\prime}$.
Hence the implied guarantee for $v$ with respect to the report $v^{\prime}$ is
not more than $\min_{\\{B\;|\;z_{B}=1\\}}[v(B)]=v(z)$. As
$\hat{s}^{\prime}_{v}(v)=s^{\prime}(v,n){=\max_{y\in{\cal{S}}}[v(y)]}\geq
v(z)\geq\hat{s}^{\prime}_{v}(v^{\prime})$ (the last inequality is not
necessarily an equality, as there might be bundles $B$ acceptable for
$v^{\prime}$ beyond those for which $z_{B}=1$), reporting $v^{\prime}$ instead
of $v$ does not increase the implied guarantee.

  3. 3.

$s^{\prime}(v,n)\geq s(v,n)$ for every valuation function $v$. This is
established by the following chain of inequalities:

$s^{\prime}(v,n)=\max_{x\in{\cal{S}}}[v(x)]\geq v(x^{v})\geq s(v,n)$

where the last inequality holds because $s$ is feasible.

$\blacksquare$

##  Appendix H Missing Proof from Section 6

###  H.1 Missing Proof from Section 6.1

###### Observation 17

For two agents with additive valuations, for any family ${\cal{F}}_{2}$, its
associated ordinal maximin share ${\cal{F}}_{2}$-maximin is feasible.
Moreover, if an optimal partition in ${\cal{F}}_{2}$ can be computed in
polynomial time for every additive valuation $v$, then acceptable allocations
can also be computed in polynomial time.

Proof. Given $m$, let ${\cal{F}}_{m,2}$ be the family of partitions from
${\cal{F}}_{2}$ that is associated with $m$. let
$P^{i}=(B^{i}_{1},B^{i}_{2})\in{\cal{F}}_{m,2}$ be an optimal partition for
agent $i$: a partition for which the ${\cal{F}}_{2}$-maximin share of agent
$i$ with valuation $v_{i}$ equals to
$\min\\{v_{i}(B^{i}_{1}),v_{i}(B^{i}_{2})\\}$. Let $PS_{2}=v_{2}({\cal{M}})/2$
be the proportional share for agent $2$. Since
$\max\\{v_{2}(B^{1}_{1}),v_{2}(B^{1}_{2})\\}\geq
PS_{2}\geq\min\\{v_{2}(B^{2}_{1}),v_{2}(B^{2}_{2})\\}$, the share is feasible
using the partition $(B^{1}_{1},B^{1}_{2})$ in which agent $2$ picks her
preferred bundle. If $P^{1}$ is computed in polynomial time, then the above
allocation algorithm also runs in polynomial time. $\blacksquare$

####  H.1.1 Proof of Proposition 7

See 7 Proof. For the family ${\cal{F}}_{n}$ of partitions and parameter $m$,
let ${\cal{F}}_{m,n}$ be the family of partitions associated with the ordinal
maximin share ${\cal{F}}_{n}$-maximin, a share which we denote by $s$. Let
$v,v^{\prime}$ be two arbitrary additive valuation functions. Recall that
$\hat{s}_{{v}}({{v^{\prime}}})$ denotes the guarantee of $s$ when the true
valuation function is $v$, and the reported valuation function is
$v^{\prime}$. To prove that ${\cal{F}}_{n}$-maximin is self maximizing we need
to show that $\hat{s}_{{v}}({{v}})\geq\hat{s}_{{v}}({{v^{\prime}}})$.

Let $P=(P_{1},\ldots,P_{n})\in{\cal{F}}_{m,n}$ be the partition (of indices)
giving $\hat{s}_{{v^{\prime}}}({{v^{\prime}}})$. That is, when items are
indexed in decreasing order of $v^{\prime}$ value, $P$ induces a partition
$(B^{\prime}_{1},\ldots,B^{\prime}_{n})$ of ${\cal{M}}$, and
$v^{\prime}(B^{\prime}_{j})\geq\hat{s}_{{v^{\prime}}}({{v^{\prime}}})$ for
every $j\in[n]$. In contrast, when items are indexed in decreasing order of
$v$ value, $P$ induces a possibly different partition of ${\cal{M}}$, and we
refer to this partition as $(B_{1},\ldots,B_{n})$. W.l.o.g., let $B_{1}$ be
such that $v(B_{1})$ is smallest. Then $v(B_{1})\leq\hat{s}_{{v}}({{v}})$,
because $\hat{s}_{{v}}({{v}})$ is determined by the best partition
${\cal{F}}_{m,n}$, and $P$ is not necessarily the best partition.

We shall use the following notation. For every $1\leq j\leq m$, recall that
$e_{j}$ denotes the $j^{th}$ largest item according to $v$ (here and
elsewhere, ties can be broken arbitrarily, without affecting correctness of
the proof), similarly, $e^{\prime}_{j}$ denotes the $j^{th}$ largest item
according to $v^{\prime}$, $E_{j}$ denotes the set $\\{e_{1},\ldots,e_{j}\\}$,
and $E^{\prime}_{j}$ denotes the set
$\\{e^{\prime}_{1},\ldots,e^{\prime}_{j}\\}$.

Let $I=\\{i_{1},\ldots i_{k}\\}$ be the set of indices in $P_{1}$, the first
part of the partition $P$. That is, $B_{1}=\\{e_{i_{1}},\ldots,e_{i_{k}}\\}$
and $B^{\prime}_{1}=\\{e^{\prime}_{i_{1}},\ldots,e^{\prime}_{i_{k}}\\}$.

Let $s_{i_{1}}$ denote the item of highest index (lowest $v$ value) among the
items of $E^{\prime}_{i_{1}}$. For every $j$ such that $2\leq j\leq k$, let
$s_{i_{j}}$ denote the item of highest index (lowest $v$ value) among the
items of $E^{\prime}_{i_{j}}\setminus\\{s_{i_{1}},\ldots,s_{i_{j-1}}\\}$.
Consider the bundle $S=\\{s_{i_{1}},\ldots,s_{i_{k}}\\}$.

We claim that $v^{\prime}(S)\geq v^{\prime}(B^{\prime}_{1})$ and that
$v(S)\leq v(B_{1})$. Assuming the claim, we infer that $S$ is a bundle
acceptable under $v^{\prime}$ (recall that
$v^{\prime}(B^{\prime}_{1})\geq\hat{s}_{{v^{\prime}}}({{v^{\prime}}})={\hat{s}(v^{\prime},n)}$),
and that $v(S)$ is not larger than the ${\cal{F}}_{n}$-maximin share for $v$
(recall that $v(B_{1})\leq\hat{s}_{{v}}({{v}})$). By reporting $v^{\prime}$
instead of the true $v$ the agent might get the bundle $S$, and hence her
implied guarantee does not improve, as $v(S)\leq
v(B_{1})\leq\hat{s}_{{v}}({{v}})$. Consequently, as this holds for any
additive $v,v^{\prime}$, the ordinal maximin share ${\cal{F}}_{n}$-maximin is
self-maximizing.

It remains to prove the claim, showing that $v^{\prime}(S)\geq
v^{\prime}(B^{\prime}_{1})$ and $v(S)\leq v(B_{1})$.

Recall that $S=\\{s_{i_{1}},\ldots,s_{i_{k}}\\}$ and that
$B^{\prime}_{1}=\\{e^{\prime}_{i_{1}},\ldots,e^{\prime}_{i_{k}}\\}$. As
$v^{\prime}(s_{i_{j}})\geq v^{\prime}(e^{\prime}_{i_{j}})$ for every $j$, we
get that $v^{\prime}(S)\geq v^{\prime}(B^{\prime}_{1})$, as desired.

It remains to show that $v(S)\leq v(B_{1})$. Recall that
$B_{1}=\\{e_{i_{1}},\ldots,e_{i_{k}}\\}$, and the notation $E_{j}$ above. We
show that for every $j\in[k]$ the set $S$ can have at most $j-1$ items from
$E_{i_{j}-1}$. First, observe that $S$ cannot have any item from
$E_{i_{1}-1}$, or equivalently, for every $j\in[k]$, the item $s_{i_{j}}$ does
not belongs to $E_{i_{1}-1}$. For $j=1$ this holds because
$|E^{\prime}_{i_{1}}|=|E_{i_{1}-1}|+1$, and hence $E^{\prime}_{i_{1}}\setminus
E_{i_{1}-1}$ contains at least one item. As every item in
$E^{\prime}_{i_{1}}\setminus E_{i_{1}-1}$ has larger index (smaller $v$ value)
than every item in $E_{i_{1}-1}$, the item $s_{i_{1}}$ will be selected from
$E^{\prime}_{i_{1}}\setminus E_{i_{1}-1}$. For $j$ such that $2\leq j\leq k$
the claim that $s_{i_{j}}\not\in E_{i_{1}-1}$ holds because the set
$E^{\prime}_{i_{j}}$ contains at least $j$ items not from $E_{i_{1}-1}$
(because $|E^{\prime}_{i_{j}}|\geq i_{1}+j-1$), and exactly $j-1$ items of
$E^{\prime}_{i_{j}}$ are selected in $S$ as
$\\{s_{i_{1}},\ldots,s_{i_{j-1}}\\}$. Hence at least one item not from
$E_{i_{1}-1}$ remains in $E^{\prime}_{i_{j}}$, and can be selected as
$s_{i_{j}}$. Hence, the item $e_{i_{1}}$ of largest $v$ value in $B_{1}$ has
at least as large value of the item of largest $v$ value in $S$. Likewise, $S$
can have at most one item from $E_{i_{2}-1}$, because for every $1\leq j\leq
k$, the set $E^{\prime}_{i_{j}}$ contains at least $j-1$ items not from
$E_{i_{2}-1}$. More generally, for every $j\in[k]$ the set $S$ can have at
most $j-1$ items from $E_{i_{j}-1}$. Hence for every $j$, as $v$ is additive,
$v(\\{e_{i_{1}},\ldots,e_{i_{j}}\\})$ is at least as large as the value of the
$j$ items of highest $v$ value in $S$. As $|S|=|B_{1}|$, this implies that
$v(S)\leq v(B_{1})$, as desired. $\blacksquare$

###  H.2 Proof of Theorem 6

We next present the claims that were missing in Section 6.3 to complete the
proof of Theorem 6.

###### Lemma 18

For the class of additive valuations and for every values of $n$ and $1\leq
q\leq n$, an optimal partition in ${\cal{F}}_{n,q}$ (that gives the value of
the $NS_{n,q}$ share) can be computed in time polynomial in $m$ and $n$.

Proof. Consider a valuation function $v$ over $m$ items. For simplicity of the
presentation, we present a polynomial time algorithm for computing an optimal
$NS_{n,q}(v)$ partition only in the most difficult case, that of $q=n$. The
algorithm can be adapted in a straightforward way to compute optimal
$NS_{n,q}(v)$ partitions for values of $q$ that are smaller than $n$ (in the
table $T$ described below, for every $i<n-q$, only fill up entries $T_{i,j}$
with $j=i$), and its running time only improves as $q$ becomes smaller.

Sort the items by their $v$ values. This takes time $O(m\log m)$. We assume
for simplicity that the value of $NS_{n,n}(v)$ is known, and the goal is only
to compute a partition that certifies this value. This assumption can be made
without loss of generality. For example, observe that $NS_{n,n}(v)$ must be
equal to the value of a bundle $B$ that is composed of a set of consecutive
items from the prefix $Z$ and a set of consecutive items from the suffix $S$.
As there are at most $O(m^{4})$ possible such bundles, there are at most
$O(m^{4})$ candidate values for $NS_{n,n}(v)$. We can run binary search on
these candidate values so as the find the highest candidate value for which an
$NS_{n,n}(v)$ partition exists.

Given a candidate value $c$ for $NS_{n,n}(v)$, to check whether there is a
partition in ${\cal{F}}_{n,n}$ of value at least $c$, run the following
dynamic programming algorithm. The algorithm maintains a table $T$ with $n$
rows (numbered 1 to $n$) and $m+1$ columns (numbered 0 to $m$), whose entries
are integers in the range $[-1,m]$. Entry $T_{i,j}$ is the smallest legal
value value $t$, where $t$ is legal if $t+j\leq m$ and the following holds:
one may create bins $B_{1},\ldots,B_{i}$ that contain a consecutive partition
$(Z_{1},\ldots Z_{i})$ of the first $j$ items, and a consecutive partition
$(S_{i},\ldots,S_{1})$ of the last $t$ items, so that every bin
$B_{i}=Z_{i}\cup S_{i}$ has value at least $c$. If there is no such legal
value of $t$, then this is denoted by setting $T_{i,j}=-1$.

The entries of $T$ can be filled from row 1 to row $n$, and within each row
from column 0 to column $m$. Entry $T_{1,j}$ has value $t$ with the smallest
legal value of $t$ for which
$v(\\{e_{1},\ldots,e_{j}\\}\cup\\{e_{m-t+1},e_{m}\\})\geq c$. For $i>1$, entry
$T_{i,j}$ is the smallest legal value of $t$ over all choices of $0\leq
j^{\prime}\leq j$ for which
$v(\\{e_{j^{\prime}+1},\ldots,e_{j}\\}\cup\\{e_{m-t+1},\ldots,e_{m-T_{i-1,j^{\prime}}}\\})\geq
c$. The process of filling $T$ takes polynomial time, as there are $O(mn)$
entries and the value of each entry can be computed in time $O(m)$.

Once we fill the table, then we may check whether there is a partition in
${\cal{F}}_{n,n}$ of value at least $c$ by checking whether row $n$ in the
table has an entry that is not $-1$. Finding such an entry $T_{n,j}$, we can
also find a corresponding $NS_{n,n}$ partition, by backtracking the steps of
the algorithm that gave $T_{nj}$ its value. $\blacksquare$

We shall use $\rho_{n,q}(v)$ to denote the ratio between the value of the
$NS_{n,q}$ share and the MMS for additive valuation function $v$, and
$\rho_{n,q}$ to denote the infimum ratio over all additive $v$.

###### Lemma 19

For the class of additive valuations, for every $n$ and every $1\leq q\leq n$
the value of the $NS_{n,q}$ share is at least a $\frac{2n}{3n-1}$ fraction of
the MMS. In other words, $\rho_{n,q}\geq\frac{2n}{3n-1}$.

Proof. It suffices to prove the lemma for $q=1$, as then the value of the
$NS_{n,q}$ share is smallest. We may also assume that $m>n$, as otherwise the
value of the $NS_{n,1}$ share is equal to the MMS.

The proof proceeds by induction on $n$. For the base case the lemma holds,
because $NS_{n,1}$ is equal to the $MMS_{n}(v_{i})$ when $n=1$. For the
inductive step, we assume that the lemma holds for $n-1$, and prove it for
$n$.

For every additive valuation function $v_{i}$ we show a partition in
${\cal{F}}_{n,1}$ in which every bundle has value at least
$\frac{2n}{3n-1}MMS_{n}(v_{i})$. The items are ordered from largest to
smallest value. We may assume that
$v_{i}(e_{1})<\frac{2n}{3n-1}MMS_{n}(v_{i})$, as otherwise we can set
$B_{1}=\\{e_{1}\\}$, and then use the inductive hypothesis to create an
$NS_{n-1,1}$ partition for the remaining items. Every bin in this partition
has value at least $\frac{2n}{3n-1}MMS_{n}(v_{i})$, because the $MMS_{n-1}$
value for the remaining items is at least as large as the $MMS_{n}$ value for
the original items ($n-1$ bundles of the $MMS_{n}$ partition do not contain
$e_{1}$).

Place items $e_{1},\ldots,e_{n}$ in bins $B_{1},\ldots,B_{n}$, respectively,
and continue filling bins in reverse order, closing each bin once its value
reaches (or exceeds) $\frac{2n}{3n-1}MMS_{n}(v_{i})$. We may assume that
$B_{n}$ contains at least three items. It cannot contain only one item because
$v_{i}(e_{n})\leq v_{i}(e_{1})<\frac{2n}{3n-1}MMS_{n}(v_{i})$. It can be
assumed not to have only two items, because then removing $B_{n}$ does not
decrease the MMS. (This is a known fact that holds because some bundle in the
MMS partition has two of the first $n+1$ items, and the total value of items
$e_{n}$ and $e_{n+1}$ is at most the value of this pair.) Consequently, for
the remaining items we can use the inductive hypothesis to create an
$NS_{n-1,1}$ partition in which every bundle has value at least
$\frac{2n}{3n-1}MMS_{n}(v_{i})$. (For $q=1$, setting
$B_{n}=\\{e_{n},e_{n+1}\\}$ does not impose any new constraint on $NS_{n-1,1}$
for the remaining items.)

Hence $v_{i}(e_{n})+v_{i}(e_{n+1})<\frac{2n}{3n-1}MMS_{n}(v_{i})$, implying
that $v_{i}(e_{n+1})<\frac{n}{3n-1}MMS_{n}(v_{i})$. Hence no bin can have
value as high as $\frac{3n}{3n-1}MMS_{n}(v_{i})$. Hence the total value of the
last $n-1$ bins is at most $(n-1)\frac{3n}{3n-1}MMS_{n}(v_{i})$, leaving value
of at least
$(n-(n-1)\frac{3n}{3n-1})MMS_{n}(v_{i})=\frac{2n}{3n-1}MMS_{n}(v_{i})$ for
$B_{1}$. $\blacksquare$

We state some conventions that are used in all subsequent proofs. Let $v$ be
an arbitrary additive valuation function. We assume that items are sorted from
highest to lowest value (with arbitrary tie breaking). When proving lower
bounds we also assume that the MMS is 1, and that in the MMS partition, every
bundle has value exactly 1. These assumptions can be made without loss of
generality. In particular, if there is a negative example in which the MMS is
1 but the MMS partition contains a bundle of value strictly larger than 1, we
can reduce values of items in this bundle until its value becomes exactly 1,
and the approximation ratio of $NS_{n,q}$ does not improve. This is because
the value of the MMS does not change, and the value of the $NS_{n,q}$ share
does not increase, because it is an ordinal maximin share (and hence monotone
in the value of the items). We remark that in explicit examples that we give,
the MMS will often not be 1, as we prefer to have integer item values, for
readability of the examples.

In Lemma 23 we shall consider $NS_{3,2}$ and prove that for additive
valuations $\rho_{3,2}=\frac{4}{5}$. Before that, we prove several helpful
claims.

###### Lemma 20

$\rho_{2,1}=\frac{4}{5}$.

Proof. The example with item values $3,2,2,2,1$ shows that
$\rho_{2,1}\leq\frac{4}{5}$. Hence it remains to show that
$\rho_{2,1}\geq\frac{4}{5}$. If $v(e_{3})\geq\frac{2}{5}$, then $NS_{2,1}$ may
choose $B_{2}=\\{e_{2},e_{3}\\}$ and $B_{1}$ containing the remaining items,
and each bundle has value at least $\frac{4}{5}$. (For $B_{2}$ this holds
because $v(e_{2})\geq v(e_{3})$, and for $B_{1}$ this holds because
$v(B_{2})\leq 1$, as otherwise the MMS partition must contain a bundle
containing two of the top three items, with value strictly larger than 1.) If
$v(e_{3})\leq\frac{2}{5}$ then $NS_{2,1}$ can place $e_{1}$ in $B_{1}$, and
then items in $B_{2}$ until the first point in which the value of $B_{2}$
reaches or exceeds $\frac{4}{5}$. At this point, value of at least
$2-(\frac{4}{5}+\frac{2}{5})\geq\frac{4}{5}$ is left for $B_{1}$. In either
case, the value of $NS_{2,1}$ is at least $\frac{4}{5}$. $\blacksquare$

###### Lemma 21

$\rho_{2,2}=\frac{5}{6}$.

Proof. The example with item values $4,3,2,2,1$ shows that
$\rho_{2,2}\leq\frac{5}{6}$. Hence it remains to show that
$\rho_{2,2}\geq\frac{5}{6}$.

For every item $j$, we denote $v(e_{j})$ by $x_{j}$, for brevity. If there is
an example with $\rho_{2,2}<\frac{5}{6}$ (and with an MMS partition with two
bundles of value exactly 1), then it must satisfy the following constraints.

  1. 1.

$x_{2}+x_{3}\leq 1$. Otherwise the MMS partition has a bundle of value more
than 1 (as one of the parts contains two of the three items of highest value).

  2. 2.

$x_{2}+x_{3}<\frac{5}{6}$. Otherwise choose $B_{2}=\\{e_{2},e_{3}\\}$ and we
have that $v(B_{1})\geq 1$ as $x_{2}+x_{3}\leq 1$.

  3. 3.

$x_{4}>\frac{1}{3}$. Otherwise start filling up $B_{2}$ from $e_{2}$, until
the first point in time in which it reaches or exceeds $\frac{5}{6}$ (and
value of at least $\frac{5}{6}$ remains for $B_{1}$).

  4. 4.

$x_{2}<\frac{1}{2}$. Otherwise $x_{4}\leq x_{3}<\frac{1}{3}$.

  5. 5.

$x_{1}<\frac{2}{3}$. Otherwise the MMS partition has a bundle of value more
than 1 (either $\\{e_{1}\\}$ is one of the MMS bundles, and the other bundle
has value at least $3x_{4}>1$, or one of the bundles has value at least
$x_{1}+x_{4}>\frac{2}{3}+\frac{1}{3}=1$).

  6. 6.

$x_{1}+x_{2}<\frac{5}{6}$. Otherwise choose $B_{1}=\\{e_{1},e_{2}\\}$, and
value of at least $\frac{5}{6}$ remains for $B_{2}$, as
$x_{1}+x_{2}<\frac{2}{3}+\frac{1}{2}=\frac{7}{6}$.

  7. 7.

$x_{5}\leq\frac{1}{3}$. Otherwise the MMS partition has a bundle of value more
than 1 (one of the MMS bundles has at least three of the five items of highest
value, with total value at least $3x_{5}$).

Given the above constraints, we start filling up $B_{2}$ from $e_{3}$, until
the first point in time in which it reaches or exceeds $\frac{5}{6}$. At that
point $B_{2}$ must include $e_{5}$ (as $x_{3}+x_{4}\leq
x_{2}+x_{3}<\frac{5}{6}$), and as $x_{5}\leq\frac{1}{3}$, the value of $B_{2}$
is at most $\frac{7}{6}$. A value of at least $\frac{5}{6}$ remains for
$B_{1}$, as desired. $\blacksquare$

###### Lemma 22

Let $v$ be an additive valuation for which either
$v(\\{e_{2},e_{3}\\})<\frac{4}{5}\cdot MMS_{3}(v)$ or
$v(\\{e_{2},e_{3}\\})>MMS_{3}(v)$. Then $\rho_{3,1}(v)\geq\frac{4}{5}$.

Proof. For an additive valuation function $v$ and $n=3$, we write constraints
that need to hold if the value of the MMS is 1 (with an MMS partition in which
each bundle has value exactly 1, which is without loss of generality), but the
value of $NS_{3,1}$ is strictly less than $\frac{4}{5}$. The variables in our
constraints are $x_{i}$ for $i\geq 1$, where $x_{i}$ denotes the value of item
$e_{i}$ (namely, $x_{i}=v(e_{i})$).

  1. 1.

$\sum_{i}x_{i}=3$. This holds as every bundle in the MMS has value 1, and
$n=3$.

  2. 2.

$x_{1}<\frac{4}{5}$. Otherwise, take $B_{1}=\\{e_{1}\\}$, and for the
remaining items $NS_{2,2}$ applies, with value $NS_{2,2}\geq
NS_{2,1}\geq\frac{4}{5}$.

  3. 3.

$x_{3}+x_{4}<\frac{4}{5}$. Otherwise, take $B_{3}=\\{e_{3},e_{4}\\}$, and for
the remaining items use $NS_{2,1}\geq\frac{4}{5}$. (We use the fact that by
removing $\\{e_{3},e_{4}\\}$ and reducing $n$ to 2, the MMS of the resulting
instance remains at least 1 (because at least two of the top four items are in
the same bundle in the original MMS partition, and $e_{3}$ and $e_{4}$ have
lowest value among these four items).

We infer than $x_{4}<\frac{2}{5}$.

  4. 4.

$x_{5}+x_{6}+x_{7}\leq 1$. Otherwise the MMS partition contains a bundle of
value larger than 1. (This follows because some bundle in the MMS partition
contains at least three items out of the first seven items, and
$e_{5},e_{6},e_{7}$ are the items of smallest value among these seven items.)

  5. 5.

$x_{3}+x_{4}+x_{5}\geq\frac{4}{5}$. Otherwise $x_{5}\leq\frac{4}{15}$. Then,
after putting $\\{e_{3},e_{4},e_{5}\\}$ in $B_{3}$, if we close each of
$B_{3}$ and $B_{2}$ at the item at which it reaches or exceeds $\frac{4}{5}$,
none of these bundles has value larger than $\frac{16}{15}$ (recall that
$x_{2}\leq x_{1}\leq\frac{4}{5}$), and a value of at least
$\frac{13}{15}>\frac{4}{5}$ is left for $B_{1}$.

We infer that $B_{3}=\\{e_{3},e_{4},e_{5}\\}$ and $v(B_{3})\leq\frac{6}{5}$.

  6. 6.

$x_{2}+x_{6}\leq 1$. Otherwise (namely, if $x_{2}+x_{6}>1$), it must be that
$e_{1}$, $e_{2}$ and $\\{e_{3},\ldots,e_{6}\\}$ are in separate bundles in the
MMS partition (otherwise the MMS partition has a bundle of value strictly
larger than 1). Consequently, $B_{3}$ (shown above to satisfy
$B_{3}=\\{e_{3},e_{4},e_{5}\\}$) would be contained in a single bundle of the
MMS partition. As two full bundles of the MMS partition remain, the MMS (with
$n=2$) for the remaining items remains at least 1. Then, from the remaining
items, $NS_{3,2}$ can make two bundles of value at least $\frac{4}{5}$, as in
the case $NS_{2,1}$.

  7. 7.

$x_{2}+x_{6}<\frac{4}{5}$. Otherwise, make $B_{2}=\\{e_{2},e_{6}\\}$, and as
$v(B_{2})\leq 1$ (by the constraint $x_{2}+x_{6}\leq 1$) and we have the
constraint $v(B_{3})\leq\frac{6}{5}$, a value of at least $\frac{4}{5}$ is
left for $B_{1}$.

We infer that $\\{e_{2},e_{6},e_{7}\\}\subseteq B_{2}$.

If any of the above constraints are violated, then the value of $NS_{3,1}$ is
at least $\frac{4}{5}$. Hence we assume that all the above constraints hold.
Now we consider two cases, based on the allowed values of
$v(\\{e_{2},e_{3}\\})=x_{2}+x_{3}$.

  1. 1.

If $x_{2}+x_{3}\geq 1$, then recall that the last item to enter $B_{3}$ is
$e_{5}$, and the last item to enter $B_{2}$ has value not larger than $x_{7}$.
Using $x_{5}\leq x_{4}\leq\frac{4}{5}-x_{3}$ and $x_{7}\leq
x_{6}\leq\frac{4}{5}-x_{2}$ we have that the combined value of $B_{3}$ and
$B_{2}$ is at most
$(\frac{4}{5}+\frac{4}{5}-x_{3})+(\frac{4}{5}+\frac{4}{5}-x_{2})\leq\frac{16}{5}-1=\frac{11}{5}$.
This leaves for $B_{1}$ a value of $\frac{4}{5}$.

  2. 2.

If $x_{2}+x_{3}\leq\frac{4}{5}$ then $x_{3}\leq\frac{2}{5}$. If
$B_{2}=\\{e_{2},e_{6},e_{7}\\}$ then the value of $B_{2}$ and $B_{3}$ combined
is at most $\frac{11}{5}$ (as $x_{5}+x_{6}+x_{7}\leq 1$ and $x_{4}\leq
x_{3}\leq\frac{2}{5}$), and $\frac{4}{5}$ value remains for $B_{1}$. If
$B_{2}$ has at least four items, then $B_{3}$ has value at most $3x_{3}$ and
$B_{2}$ has value at most $\frac{4}{5}+\frac{1}{2}(\frac{4}{5}-x_{2})$ (this
is because the two items added to $B_{2}$ after $e_{2}$ did not give it a
value of $\frac{4}{5}$, implying that the third item of $B_{2}$ had value at
most $\frac{1}{2}(\frac{4}{5}-x_{2})$, and hence so did the item that caused
$B_{2}$ to reach or exceed $\frac{4}{5}$), for a total of at most
$\frac{6}{5}-\frac{1}{2}x_{2}+3x_{3}\leq\frac{6}{5}+\frac{5}{2}x_{3}\leq\frac{11}{5}$.
Hence again, $\frac{4}{5}$ value remains for $B_{1}$.

$\blacksquare$

###### Lemma 23

$\rho_{3,2}=\frac{4}{5}$ and thus $\rho_{3,3}\geq\frac{4}{5}$.

Proof. The instance with item values $3,3,2,2,2,2,1$ shows that
$\rho_{3,2}\leq\frac{4}{5}$. It remains to show that
$\rho_{3,2}\geq\frac{4}{5}$.

If it does not hold that $\frac{4}{5}\leq v(\\{e_{2},e_{3}\\}\leq 1$, then
$\rho_{3,1}\geq\frac{4}{5}$ by Lemma 22, and as $\rho_{3,2}\geq\rho_{3,1}$ we
conclude that $\rho_{3,2}\geq\frac{4}{5}$. If, on the other hand,
$\frac{4}{5}\leq v(\\{e_{2},e_{3}\\}\leq 1$, we can form the bundle
$B_{2}=\\{e_{2},e_{3}\\}$ in the $NS_{3,2}$ partition. As removing any two
items of total value at most 1 and decreasing $n$ by 1 does not reduce the MMS
(if they were in different bundles in the original MMS partition, then the
union of what remains from these bundles can be used as a bundle in the new
MMS partition), and as any $NS_{2,1}$ partition for the remaining items gives
(together with $B_{2}$) an $NS_{3,2}$ partition for the original instance, the
bound $\rho_{3,2}\geq\frac{4}{5}$ follows from Lemma 20 which shows that
$\rho_{2,1}=\frac{4}{5}$. $\blacksquare$

####  H.2.1 Computer assisted analysis of $\rho_{4,3}$

In this section we prove the following bound.

###### Lemma 24

$\rho_{4,3}=\frac{4}{5}$.

The inequality $\rho_{4,3}\leq\frac{4}{5}$ is proved by Example 1, thus we
only need to show that $\rho_{4,3}\geq\frac{4}{5}$.

Our proof that $\rho_{4,3}\geq\frac{4}{5}$ is based on constructing a mixed
integer linear program (MILP) that searches for a valuation $v$ that minimizes
the ratio between $NS_{4,3}$ and the MMS (with $n=4$) for $v$. As we shall
prove (see Lemma 25), it suffices to consider instances with up to 14 items.

The MILP searches for an instance with an MMS partition into four bundles,
each of value exactly 5. It attempts to minimize $z$, which represents the
value of $NS_{4,3}$. It contains the variables $x_{1}\geq\ldots,x_{14}\geq 0$
for the values of the items. It also contains binary decision variables
$y_{j}$. We write the constraints (and comments explaining them) in the syntax
of the online optimizer appspot (https://online-optimizer.appspot.com/), so
that readers can simply run the program. (A text file containing the full
program can be obtained from the authors upon request.)

    var x1 >= 0;
    ...
    var x14 >= 0;

    var z >= 0;

    var y1>=0, binary;
    ...
    var y45>=0, binary;

    minimize ns:     z;

    subject to

    o1: x1 >= x2;
    ...
    o13: x13 >= x14;

The MMS partition imposes the following constraints. Constraint a0 follows
from having an MMS partition with four disjoint bundles, each of value 5. The
other constrain express the fact that for every $k\geq 0$ and $1\leq j\leq 3$,
there are $j$ bundles in the MMS partition that together contain $jk+j$ of the
first $4k+j$ items, and that the value of these $jk+j$ items (even if these
are the least valuable) must be at most $5j$.

    a0: x1 + x2 + x3 + x4 + x5 + x6 + x7 + x8 + x9 + x10 + x11 + x12 + x13 + x14 = 20;
    a1: x1 <= 5; /* k=0 and j=1 */
    a2: x4 + x5 <= 5; /* k=1 and j=1 */
    a3: x3 + x4 + x5 + x6 <= 10; /* k=1  and j=2 */
    a4: x2 + x3 + x4 + x5 + x6 + x7 <=  15; /* k=1 and j=3 */
    a5: x7 + x8 + x9 <= 5; /* k=2 and j=1 */
    a6: x5 + x6 + x7 + x8 + x9 + x10 <= 10; /* k=2 and j=2 */
    a7: x3 + x4 + x5 + x6 + x7 + x8 + x9 + x10 + x11 <= 15; /* k=2 and j=3 */
    a8: x10 + x11 + x12 + x13 <= 5; /* k=3 and j=1 */
    a9: x7 + x8 + x9 + x10 + x11 + x12 + x13 + x14 <= 10; /* k=3 and j=2 */

For the next set of constraints, we show that if they do not hold then $z\geq
4$. We shall use the fact that whenever two items of total value not larger
than the MMS are removed, the MMS for the remaining items (when $n$ is smaller
by one) does not decrease.

    b1: x1 <= 4;
    b2: x4 + x5 <= 4;
    b3: x6 + x7 + x8 >= 4;
    b4: x7 >= 1;
    b5: x3 + x6 <= 5;
    b6: x2 + x9 <=  5;

The above constraints are justified as follows:

  * •

b1: otherwise choose $B_{1}=\\{e_{1}\\}$. For the remaining items, take the
best $NS_{3,3}$ partition. Then $z\geq 4$, because for the remaining items
$MMS_{3}(v)\geq 5$, and $\rho_{3,3}\geq\frac{4}{5}$ by Lemma 23.

  * •

b2: otherwise (in fact, even if $x4+x5\geq 4$ rather than $x4+x5>4$), there
are two cases to consider. If $x2+x3\leq 5$ choose $B_{2}=\\{e_{2},e_{3}\\}$
and $B_{3}=\\{e_{4},e_{5}\\}$ (note that $x2+x3\geq x4+x5\geq 4$), and for the
remaining items reduce to $NS_{2,1}$. If $x2+x3>5$, choose
$B_{4}=\\{e_{4},e_{5}\\}$, and for the remaining items take the best
$NS_{3,1}$ partition (in particular, this will enforce $e_{1}\in
B_{1},e_{2}\in B_{2},e_{3}\in B_{3}$). By Lemma 22 (which is applicable
because $x2+x3>5$), every bundle in this partition will have value at least 4.

  * •

b3: otherwise, consider an $NS_{4,1}$ partition in which we first put items
$e_{1},e_{2},e_{3},e_{4}$ in bins $B_{1},B_{2},B_{3},B_{4}$ respectively, and
then continue inserting items in decreasing order of value into the bins
$B_{4}$ to $B_{1}$, where each bin becomes closed (and then we move to the
next bin) once its value reaches or exceeds 4.

In the above $NS_{4,1}$ partition, the last item in $B_{4}$ is no earlier than
$e_{6}$ (due to b2, and the fact that its justification also implies that we
may assume that $x4+x5<4$). Consequently, if b3 does not hold, then the sum of
values of last item in bins ${B_{2}},B_{3},B_{4}$ is at most 4, and
consequently their total value is at most $3\cdot 4+4=16$. Hence a value of at
least 4 remains for $B_{1}$.

We remark that b3 also implies that $x_{4}+x_{5}+x_{6}\geq 4$ (by monotonicity
of item values), and together with b2 (and its justification), we deduce that
in an $NS_{4,1}$ partition one should take $B_{4}=\\{e_{4},e_{5},e_{6}\\}$.

  * •

b4: otherwise, choose an $NS_{4,1}$ partition (as explained in the
justification for b3) with $B_{4}=\\{e_{4},e_{5},e_{6}\\}$. As each of the
remaining bins becomes closed once its value reaches or exceeds 4, the value
in the bin will be less than 5 (if b4 does not hold. then the last item in
each of these bins has value less than 1). As $v(B_{4})\leq 6$, each of the
remaining bins will indeed reach a value of at least 4.

  * •

b5: otherwise, none of $e_{1},e_{2},e_{3}$ can be in the same bundle as one of
$e_{4},e_{5},e_{6}$ in the MMS partition, and hence $e_{4},e_{5},e_{6}$ are in
the same bundle in the MMS partition. If $4\leq x2+x3\leq 5$ choose
$B_{2}=\\{e_{2},e_{3}\\}$ and $B_{3}=\\{e_{4},e_{5},e_{6}\\}$, and for the
remaining items reduce to $NS_{2,1}$. Else, choose
$B_{4}=\\{e_{4},e_{5},e_{6}\\}$, and for the remaining items reduce to
$NS_{3,1}$ using Lemma 22.

  * •

b6: otherwise, none of $e_{1},e_{2}$ can be in the same bundle as one of
$e_{3},\ldots,e_{9}$ in the MMS partition, and consequently
$e_{3},\ldots,e_{9}$ fit in two MMS bundles. Choose
$B_{4}=\\{e_{4},e_{5},e_{6}\\}$ and put $e_{3},e_{7},e_{8},e_{9}$ in $B_{3}$.
If by this $B_{3}$ has value at least 4, continue with an $NS_{2,1}$ partition
for the remaining items. If this $B_{3}$ has value at most less than 4, then
$x_{9}<1$, and then in the $NS_{4,1}$ partition presented in the justification
for b3, only $B_{4}$ might have value above 5 (and no more than 6, by b2).
Hence no bin has value less than 4 (because the sum of their values is 20).

Each of the above constraints (in groups a and b) captures a condition that
must hold independently of other constraints. We next present some other
constraints that capture a logical _OR_ over several basic constraints,
implied by the assumption that there is an MMS partition into four bundles,
each of value 5. For example, one set of constraints (group d below) captures
the constraint that “From the first seven items, either $x2+x7\leq 5$ (when
every bundle has at most two items), or $x5+x6+x7\leq 5$ (when some bundle has
three items)”. A basic constraint like “$x2+x7\leq 5$” is captured by the
constraint “$x2+x7-20*y4\leq 5$”, such that if the indicator $y4$ is $0$ then
the basic constraint must hold (and if $y4=1$ it might not). To enforce a
logical _OR_ over $k$ basic constraints, we require that the sum of the $k$
indicators be at most $k-1$, so at least one indicator must be $0$ (this is
captured by constraint numbered 0 in each group).

We next present three groups of constraints (c, d and f), each corresponds to
a logical _OR_ , each regarding the values for some prefix of items.

    c1: x2 + x6 - 20*y1 <= 5;
    c2: x5 + x6 + x9 - 20*y2 <= 5;
    c3: x6 + x7 + x8 + x9 - 20*y3  <= 5;
    c0: y1 + y2 + y3 <= 2;

    d1: x2 + x7 - 20*y4 <= 5;
    d2: x5 + x6 + x7 - 20*y5 <= 5;
    d0: y4 + y5 <= 1;

    f1: x2 + x8 - 20*y6 <= 5;
    f2: x3 + x7 + x8 - 20*y7  <= 5;
    f3: x5 + x6 + x7 + x8 - 20*y8  <= 5;
    f0: y6 + y7 + y8 <= 2;

The above constraints are justified as follows:

  * •

Group c: among the first nine items, the MMS partition either has a bundle of
size at least four (and then c3 holds), or at least two bundles of size three
(and then c2 holds: at least out of the first six items must be in the same
bundle of size three, together with one more item of value at least $x_{9}$),
or one bundle of size three and three pairs, and then either c2 holds (if only
one of $e7,e8,e9$ is in a bundle of size three) or c1 holds (if at least two
of $e7,e8,e9$ are in a bundle of size three, then at least one of
$e_{1},e_{2}$ is not in a bundle with any of the items $e7,e8,e9$).

  * •

Group d: among the first seven items, the MMS partition either has a bundle of
size at least three (and then d2 holds), or has three bundles of size two (and
then d1 holds).

  * •

Group e: among the first eight items, the MMS partition either has a bundle of
size four (and then f3 holds), or has two bundles of size three (and then f2
holds), or has at least three bundles of size at least two (and then f1
holds).

The above set of constraints can naturally be extended to corresponding
constraints when there are $m>14$ items. This involves the following
modifications. For every $i$ such that $14<i\leq m$ we introduce a non-
negative variable $x_{i}$ to denote the value of item $e_{i}$. For every $i$
such that $14\leq i<m$ we add the constraint $o_{i}:x_{i}\geq x_{i+1}$.
Finally, we replace the constraint $a_{0}$ by the constraint
$\sum_{i=1}^{m}x_{i}=20$.

We are now ready to explain why we can assume that the number of items is at
most 14.

###### Lemma 25

If for $n=4$ there exists an additive valuation $v$ over $m>14$ items such
that $NS_{4,3}(v)<4$ and the constraints above (when extended to $m$ items)
hold, then there exists an additive valuation $v^{\prime}$ over $14$ items
such that $NS_{4,3}(v^{\prime})\leq NS_{4,3}(v)<4$ and the constraints above
hold.

Proof. The constraints of types a, c, d and f are implied by having an MMS
partition in which every bundle has value 5, but do not force the instance to
have such a partition. Suppose now that there is an instance $I$ with $m\geq
15$ items that satisfies the above constraints and for which $NS_{4,3}<4$
(which implies that also all constraints of type b are satisfied). Then we
claim that we can merge $e_{1}$ and $e_{m}$ to a new item of value
$v(\\{e_{1},e_{m}\\})$ (replacing $e_{1}$), and the new instance $I^{\prime}$
will still satisfy all above constraints. Applying the same argument
recursively will result in an instance with $14$ items.

The only constraints involving $e_{1}$ are o1, a0, a1 and b1. They are all
assumed to hold in $I$, and we need to prove that they hold in $I^{\prime}$.

  * •

Constraint o1 holds in $I^{\prime}$, as $x_{1}$ increased.

  * •

Constraint a0 (if $m>14$, the interpretation is that the sum does not stop at
$x_{14}$, but rather includes all items up to $x_{m}$) holds in $I^{\prime}$
because the value lost by $e_{m}$ was added to $e_{1}$.

  * •

As to constraint a1, we consider two cases. If $x_{m}\geq 1$, then consider
the surplus of items in $I$, where for every item $e_{i}$ its surplus is
defined as $x_{i}-1$ (note that the assumption $x_{m}\geq 1$ implies that the
surplus is non-negative). If a1 is violated in $I^{\prime}$, then
$x_{1}+x_{m}>5$ in $I$, and the total surplus of $\\{e_{1},e_{m}\\}$ is more
than 3. Constraint b3 implies that the total surplus of
$\\{e_{6},e_{7},e_{8}\\}$ (and hence also of $\\{e_{3},e_{4},e_{5}\\}$) is at
least $4-3=1$. Thus the total surplus of items in $I$ is greater than 5, and
consequently the sum of item values in $I$ is strictly larger than $15\cdot
1+5=20$, contradicting constraint a0 (total value of 20). Hence a1 holds in
$I^{\prime}$ if $x_{m}\geq 1$. It remains to consider the case that $x_{m}<1$.
In this case a1 follows because originally $x_{1}\leq 4$, by constraint b1.

  * •

Constraint b1 holds in $I^{\prime}$, as otherwise in the original instance $I$
we could form a bundle $B_{1}=\\{e_{1},e_{m}\\}$, and its value would be at
least 4 but no more than 5 (as a1 holds in $I^{\prime}$). For the remaining
items, we can take the best $NS_{3,3}$ partition, creating bundles
$B_{2},B_{3},B_{4}$, each of value at least 4 (because for the remaining items
$MMS_{3}(v)\geq 5$, and $\rho_{3,3}\geq\frac{4}{5}$ by Lemma 23). This
contradicts the assumption that $NS_{4,3}<4$ for instance $I$.

For every $q$, every $NS_{4,q}$ partition of $I^{\prime}$ induces one of the
same value for $I$, and so if $NS_{4,3}<4$ for $I$, the same holds for
$I^{\prime}$. $\blacksquare$

The remaining set of constraints (group n) consider various $NS_{4,3}$
partitions, and for each such partition binary decision variables are used to
express the requirement that at least one of the bundles has value not larger
than $z$ (a logical _OR_). The constraints of type $p_{ij}$ identify various
bundles that can be placed in bin $B_{i}$. The corresponding decision variable
is indexed by the index of the constraint, for convenience. Each constraint of
type $n_{j}$ considers one possible $NS_{4,3}$ partition. The index $j$ is a
concatenation of the second indices of the $y$ variables in the constraint.

    p41: x4 + x5 + x6 - 20*y41 <= z;
    p42: x5 + x6 + x7 - 20*y42 <= z;
    p43: x6 + x7 + x8 - 20*y43 <= z;
    p44: x7 + x8 + x9 - 20*y44 <= z;
    p45: x7 + x8 + x9 + x10 + x11 + x12 + x13 - 20*y45 <= z;

    p31: x3 + x4 - 20*y31 <= z;
    p32: x3 + x7 - 20*y32<= z;
    p33: x3 + x7 + x8 - 20*y33 <= z;
    p34: x4 + x5 + x9 - 20*y34 <= z;
    p35: x4 + x5 + x9 + x10 - 20*y35 <= z;
    p36: x4 + x5 + x6 - 20*y36 <= z;
    /* mathematically, y41 can serve instead of y36, but introducing y36 unifies notation */

    p21: x2 + x3 - 20*y21 <= z;
    p22: x2 + x3 + x10 - 20*y22 <= z;
    p23: x2 + x8 - 20*y23 <= z;
    p24: x2 + x8 + x9 - 20*y24 <= z;
    p25: x2 + x9 - 20*y25 <= z;
    p26: x2 + x9 + x10 - 20*y26 <= z;
    p27: x2 + x3 + x11 + x12 - 20*y27 <= z;

    p11: x1 + x9 + x10 + x11 + x12 + x13 + x14 - 20*y11 <= z;
    p12: x1 + x10 + x11 + x12 + x13 + x14 - 20*y12 <= z;
    p13: x1 + x11 + x12 + x13 + x14 - 20*y13 <= z;
    /* p14: x1 + x12 + x13 + x14 - 20*y14 <= z; */
    p15: x1 + x13 + x14 - 20*y15 <= z;
    p16: x1 + x14 - 20*y16 <= z;

    n1312: y11 + y23 + y31 + y42 <= 3;
    n1321: y11 + y23 + y32 + y41 <= 3;
    n2164: y12 + y21 + y36 + y44 <= 3;
    n2412: y12 + y24 + y31 + y42 <= 3;
    n2531: y12 + y25 + y33 + y41 <= 3;
    n3243: y13 + y22 + y34 + y43 <= 3;
    n3631: y13 + y26 + y33 + y41 <= 3;
    n5753: y15 + y27 + y35 + y43 <= 3;
    n6165: y16 + y21 + y36 + y45 <= 3;

Solving this mixed integer linear program (MILP) gives a valuation $v$ that
minimizes $z$, where the constraints enforce that $z\leq NS_{4,3}$ and that
the MMS is at most $5$. Running the MILP with all the above constraints
produces the instance with value $z=4$ and item values $4,4,2,2,2,2,1,1,1,1$.
As the minimum value of the MILP is $z=4$, we conclude that
$\rho_{4,3}=\frac{4}{5}$ as claimed. We remark that for this instance it holds
that $NS_{4,3}=NS_{4,2}=5$, but via an $NS_{4,3}$ partition not considered by
any of our constraints of type n (the constraints of the MILP force the
inequality $z\leq NS_{4,3}$, but not necessarily as an equality). However, as
we know of examples in which the MMS is 5 and $NS_{4,3}=4$, there is no point
in strengthening the MILP by additional constraints – its value will not
increase beyond 4.

###  H.3 Tightness

We next show that the our analysis of $\rho$ for which the share $NS_{n,q}$ is
$\rho$-dominating is tight up to low order terms.

###### Proposition 26

For every $\epsilon>0$ and fixed $q\geq 1$, there is sufficiently large $n$
and an additive valuation function for which the $NS_{n,q}$ share does not
provide an agent more than $\frac{2}{3}+\epsilon$ times her MMS.

Proof. We focus first on the case $q=1$, and later we will address the case
$q>1$. The valuation function that we describe is taken from [7], and so is
the proof regarding its MMS value.

Let $k=\lceil\frac{1}{2\epsilon}\rceil$, let
$n=\sum_{i=0}^{k}4^{i}=\frac{4^{k+1}-1}{3}$, and consider a set of
$m=3\cdot\sum_{i=0}^{k}4^{i}=4^{k+1}-1$ items ${\cal{M}}=\big{\\{}(a,b,c)\mid
a\in\\{0,1,\ldots,k\\},b\in\\{1,2,3\\},c\in\\{1,2,\ldots,4^{a}\\}\big{\\}}$.
The value of item $(a,b,c)$ is $1-\frac{a}{2k}$ if $b=1$, and $\frac{a}{2k}$
if $b\neq 1$. We call items with $b=1$ large items, and items with
$b\in\\{2,3\\}$ small items. For every $0\leq i\leq k$, we refer to the items
with $a=i$ as belonging to group $i$. Hence group $i$ contains $4^{i}$ large
items and $2\cdot 4^{i}$ small items.

We show that in the partition formed by $NS_{n,1}$, bundle $B_{1}$ is composed
of the three items of group $0$, and hence has value $1+0+0=1$, implying that
$NS_{n,1}=1$. In the $NS_{n,1}$ partition, every bundle receives a single
large item (as every large items have value at least half, while every small
item has value less than half). After the allocation of the large items, the
$NS_{n,1}$ partition allocates the small items in decreasing order of the
groups. Each bundle that received a large item of group $i$ also receives two
small items of the same group. Thus, bundle $B_{1}$ will not get another item
until all items but the small items of group $0$ are allocated.

In contrast, the MMS is at least $\frac{3}{2}-\epsilon$. This holds because
the items can be partitioned into $n$ bundles, each with value at least
$\frac{3}{2}-\epsilon$. For each $a\in\\{1,2,\ldots,k\\}$, create $2\cdot
4^{a-1}$ bundles by taking two large items of group $a$ and one small item of
group $a-1$. The value of such a bundle is
$2(1-\frac{a}{2k})+\frac{a-1}{2k}=2-\frac{a+1}{2k}\geq\frac{3}{2}-\epsilon$.
In addition, create $\frac{2\cdot 4^{k}-2}{3}$ bundles, each containing three
small items of group $k$, and each such bundle has a value of $\frac{3}{2}$.
Note that $2\cdot 4^{k}-2$ is divisible by $3$. Finally, create another bundle
using the two remaining small items of group $k$, and the large item of group
$0$. That bundle has value of $2$. The number of bundles created is

$\sum_{a=1}^{k}2\cdot 4^{a-1}+\frac{2\cdot 4^{k}-2}{3}+1=\frac{2\cdot
4^{k}-2}{3}+\frac{2\cdot 4^{k}+1}{3}=n,$

which concludes the proof.

Now we address the case that $q>1$. In this case, we require that $n\geq 2q$
(and not just $n\geq q$). As group $k$ contains over half the items, then also
for the optimal $NS_{n,q}$ partition, in order that every bin will have value
at least 1 it will still be necessary that each of the last $q$ bins contains
three items from group $k$. Thereafter, the rest of the bins are filled up
exactly as in the case of $NS_{n,1}$, again resulting in $B_{1}$ having value
1. $\blacksquare$

####  H.3.1 Additional Approximation bounds for Nested Shares

The following proposition presents several examples that provide upper bounds
on the approximation ratios obtained by the nested share $NS_{n,q}$, for some
values of $n$ and $q$. It shows that reaching a $\frac{4}{5}$ approximation
for $n=3$ requires using $NS_{3,2}$, and $NS_{3,1}$ does not suffice.
Moreover, it shows that the bound of $\frac{4}{5}$ does not extend to
$NS_{4,2}$. Finally, we observe that Example 1 shows that even the best
possible value of $q$, namely $q=n$, does not offer a better than
$\frac{4}{5}$ approximation to the MMS, when $n\geq 3$.

###### Proposition 27

There are additive valuation functions illustrating the following upper bounds
on the ratio within which $NS_{n,q}$ approximates the MMS:

  1. 1.

$\rho_{2,2}\leq\frac{5}{6}$. $\rho_{3,3}\leq\frac{5}{6}$.

  2. 2.

$\rho_{3,1}\leq 0.77$.

  3. 3.

$\rho_{4,2}\leq\frac{3}{4}$. More generally, $\rho_{n,n-2}\leq\frac{3}{4}$ for
all $n\geq 4$.

  4. 4.

$\rho_{n,n}\leq\frac{4}{5}$ for all $n\geq 4$.

Proof. For the following additive valuation function the value of $NS_{2,2}$
is 5, whereas the MMS is 6. The item values in non-increasing order are
$4,3,2,2,1$. To get a similar example for $NS_{3,3}$, add a single item of
value 6.

For the following additive valuation function the value of $NS_{3,1}$ is
0.7693, whereas the MMS is 1. The item values in non-increasing order are:

0.4615, 0.4615, 0.3846, 0.3846, 0.3846, 0.3077, 0.3077, 0.1539, 0.1539.

The MMS partition is
$\\{(e_{1},e_{3},e_{8}),(e_{2},e_{4},e_{9}),(e_{5},e_{6},e_{7})\\}$. To get to
0.7693, the $NS_{3,1}$ is forced to create the bundle $(e_{3},e_{4},e_{5})$,
and then $(e_{2},e_{6},e_{7})$, but then the items that remain have total
value only 0.7693.

For the following additive valuation function the value of $NS_{4,2}$ is 6,
whereas the MMS is 8. The item values in decreasing order are: 4, 4, 3, 3, 3,
3, 3, 3, 2, 2, 2. We next extend this example to prove that
$\rho_{n,n-2}\leq\frac{3}{4}$ for all $n\geq 4$. Consider an instance with two
items of value 4, with $2(n-1)$ items of value 3, and with $n-1$ items of
value 2. The MMS is 8, as the MMS partition can have one bundle of the form
$(4,4)$, and $n-1$ bundles of the form $(3,3,2)$. In contrast, $NS_{n,n-2}\leq
6$. In any $NS_{n,n-2}$ partition, each item of value 4 belongs to different
bundle. For each of these two bundles to have value more than 6, the four last
items must be contained in these bundles. This leaves at most
$2(n-1)+(n-1)-4=3n-7$ items of value 3 and 2. In any partition of these items
to $n-2$ bundles, there must be a bundle with at most two items. As each of
these items has value at most 3, the value of some bundle is at most 6.

Finally, an example for which $NS_{4,4}\leq\frac{4}{5}$ is provided in Example
1. The example extends to every $n>4$ by adding $n-4$ items of value $5$,
giving an instance with MMS of value 5, and $NS_{n,n}=4$ (as each additional
item will be in a different bundle). Thus, for $\rho>4/5$ the share $NS_{n,n}$
does not $\rho$-dominate the MMS. (We note that Example 1 does not apply to
$NS_{3,3}$. The natural way to adapt it to $NS_{3,3}$ is to have item values
$(3,3,2,2,2,2,1)$. However, in this case
$\\{(e_{5},e_{6},e_{7}),(e_{1},e_{4}),(e_{2},e_{3})\\}$ is an $NS_{3,3}$
partition with value 5. In this $NS_{3,3}$ partition, bin $B_{1}$ contains
items from the suffix but no items from the prefix.)

$\blacksquare$


A<EMAIL_ADDRESS>J. C<EMAIL_ADDRESS>††thanks:

# An elliptic curve over $\mathbb{Q}(u)$ with torsion $\mathbb{Z}/4\mathbb{Z}$
and rank $6$

Andrej Dujella  Department of Mathematics
Faculty of Science
University of Zagreb
Bijenička cesta 30, 10000 Zagreb, Croatia  [ Juan Carlos Peral  Departamento
de Matemáticas
Universidad del País Vasco
Aptdo. 644, 48080 Bilbao, Spain  [

###### Abstract.

In this paper, we present the construction of an elliptic curve over
$\mathbb{Q}(u)$ with torsion group $\mathbb{Z}/4\mathbb{Z}$ and rank $6$.
Previously only rank $5$ examples for such curves were known.

###### Key words and phrases:

Elliptic curves, rank, torsion group

###### 1991 Mathematics Subject Classification:

11G05

Dedicated to Marko Tadić on the occasion of his $70$th birthday

##  1\. Introduction

Let $E$ be an elliptic curve over $\mathbb{Q}$. By the Mordell-Weil theorem,
the group $E(\mathbb{Q})$ of rationals points on $E$ is a finitely generated
Abelian group. Hence, it has the form $E(\mathbb{Q})\cong E(\mathbb{Q})_{\rm
tors}\times{\mathbb{Z}}^{r}$, where $E(\mathbb{Q})_{\rm tors}$ is called the
torsion group of $E$, and the non-negative integer $r$ is called the rank of
$E$.

In 1978, Mazur [16] proved that there are precisely $15$ possible torsion
groups for elliptic curves over $\mathbb{Q}$:

$\displaystyle\mathbb{Z}/k\mathbb{Z},$ for $k=1,2,3,4,5,6,7,8,9,10,12$,
$\displaystyle\mathbb{Z}/2\mathbb{Z}\times\mathbb{Z}/k\mathbb{Z},$ for
$k=2,4,6,8$.

On the other hand, it is not known which values of rank $r$ are possible for
elliptic curves over $\mathbb{Q}$. It has been conjectured that there exist
elliptic curves of arbitrarily high rank, even that for each of the torsion
groups in Mazur’s theorem, there exist curves with that torsion group and
arbitrarily large rank. However, there are also recent heuristic arguments
that suggest the boundedness of the rank of elliptic curves. According to this
heuristic, only a finite number of curves would have rank higher than 21 (see
[17]). The current record is an example of an elliptic curve over $\mathbb{Q}$
with rank $\geq 28$, found by Elkies in 2006 (see [6] and also [14] where it
is shown that, assuming the generalized Riemann hypothesis, Elkies’s curve has
rank equal to $28$).

The first step in finding elliptic curves with large rank is usually
constructing a parametric family of elliptic curves, i.e. an elliptic curve
over the field of rational function $\mathbb{Q}(u)$, with the considered
property (e.g. with a given torsion group). Thus, it is of interest to
construct elliptic curves over $\mathbb{Q}(u)$ with a given torsion group and
relatively large generic rank.

In this paper, we will present the construction of an elliptic curve over
$\mathbb{Q}(u)$ with torsion group $\mathbb{Z}/4\mathbb{Z}$ and rank $6$,
which is the current record for the rank over $\mathbb{Q}(u)$ for this torsion
group. Let us mention that the largest known rank for an elliptic curve with
torsion group $\mathbb{Z}/4\mathbb{Z}$ over $\mathbb{Q}$ is $13$ (see [7]).
Information on current rank records for all $15$ possible torsion groups can
be found in [1].

##  2\. General equation of curves with torsion group $\mathbb{Z}/4\mathbb{Z}$

The general model of an elliptic curve with torsion group
$\mathbb{Z}/4\mathbb{Z}$ is given by

$Y^{2}+aXY+abY=X^{3}+bX^{2},$

where $ab(a^{2}-16b)\neq 0$ (see, e.g. [6]). A torsion point of order $4$ in
this model is $(0,0)$.

We will use the construction of Elkies [6] for curves with torsion group
$\mathbb{Z}/4\mathbb{Z}$. Elkies noticed that this torsion and rank $4$ can be
obtained for some elliptic $K3$ surfaces. In this case, the maximum rank is
obtained with the following types of reducible fibers for such a surface: four
of type $I_{4}$, two of type $I_{2}$ and four of type $I_{1}$, so giving a
contribution to the Néron-Severi group of $4(4-1)+2(2-1))=14$, hence the rank
over this surface is at most $20-2-14=4$ (since the Néron-Severi rank of a
$K3$ surface is at most 20, see, e.g. [18]). So in this sense, the Elkies
example is optimal.

##  3\. Elkies model for rank $4$

By the result of Inose [10], we know that the Néron-Severi rank can be 20 only
if the corresponding discriminant is one of the thirteen discriminants of
imaginary quadratic orders of class number 1. Elkies [6] has shown that the
discriminant $-163$ surface does have an elliptic model that attains rank $4$
with torsion group $\mathbb{Z}/4\mathbb{Z}$ for the following values of
parameters $a$ and $b$:

$\displaystyle a$ $\displaystyle=(8t-1)(32t+7),$ $\displaystyle b$
$\displaystyle=8(t+1)(15t-8)(31t-7).$

With a simple change of variables, the surface can be written as

$Y^{2}=X^{3}+(a^{2}-8b)X^{2}+16b^{2}X.$

Inserting the values of $a$ and $b$ given above, one gets the following
elliptic $K3$ surface $E$

$\displaystyle E:\,\,Y^{2}$
$\displaystyle=X^{3}+(65536t^{4}-17472t^{3}-10176t^{2}+18672t-3535)X^{2}$
$\displaystyle\,\,\,\mbox{}+1024(t+1)^{2}(15t-8)^{2}(31t-7)^{2}X.$

It has torsion group $\mathbb{Z}/4\mathbb{Z}$ and rank $4$. A torsion point of
order $4$ in this model is

$(32(t+1)(15t-8)(31t-7),2^{5}(1+t)(-1+8t)(-8+15t)(-7+31t)(7+32t))$

and the $X$-coordinates of four independent points of infinite order are

$\displaystyle X_{1}$ $\displaystyle=-361(t+1)(31t-7),$ $\displaystyle X_{2}$
$\displaystyle=-4(t+1)(15t-8)(16t-7)^{2},$ $\displaystyle X_{3}$
$\displaystyle=-16(t+1)(8t+7)^{2}(15t-8),$ $\displaystyle X_{4}$
$\displaystyle=4(15t-8)(16t+1)^{2}(31t-7).$

In [7], it is quoted that for

$\displaystyle a$ $\displaystyle=4(9+80t),$ $\displaystyle b$
$\displaystyle=1/2(-2+t)(-81+2t)(-1+2t)(-1+18t).$

the resulting $K3$ surface also has rank $4$.

Previous to the Elkies construction in 2007, in 2004, Kihara [12, 13] and
Lecacheux [15] found curves with rank $4$ and $5$ over $\mathbb{Q}(u)$. The
coefficients in the Kihara and Lecacheux constructions are much larger than
those in Elkies examples, and so they are less suited for finding particular
good examples of high-rank curves. In fact, the family with rank $4$ in the
Elkies paper is $y^{2}=x^{3}+A(t)x^{2}+B(t)x$, where $A(t)$ is a polynomial of
degree $4$ and $B(t)$ is a polynomial of degree $6$, and the examples with
rank $5$ have polynomial coefficients of degree $8$ and $16$, while the
corresponding coefficients in the Kihara family have degrees $52$ and $102$,
respectively. In 2016, Khoshnam and Moody [11] gave an example of rank $5$
over $\mathbb{Q}(u)$ with a simpler version of the Kihara method. In fact, the
coefficients $A$ and $B$ in this curve are polynomials of degrees $19$ and
$38$, respectively.

The object of this note is to construct an example of an elliptic curve over
$\mathbb{Q}(u)$ with torsion $\mathbb{Z}/4\mathbb{Z}$ and rank $6$. It will be
obtained as a specialization of the Elkies surface.

##  4\. A curve over $\mathbb{Q}(u)$ with torsion $\mathbb{Z}/4\mathbb{Z}$ and
rank $6$

Elkies [6] mentions, without explicitly writing such examples, that there are
several quadratic sections giving curves over $\mathbb{Q}(u)$ with rank $5$
for this torsion and several combinations of pairs of quadratic sections
leading to infinite families of curves with rank $6$ parametrized by the
points of elliptic curves of positive rank.

In [5], we made explicit the ideas of Elkies, and presented there $25$
elliptic curves over $\mathbb{Q}(u)$ with rank $5$ and several infinite
families of curves with rank $6$ parametrized by elliptic curves with positive
rank.

Now we have many more examples of quadratic sections over $\mathbb{Q}(u)$
leading to rank $5$ curves. In one of these curves, we found a further
quadratic section leading to the curve over $\mathbb{Q}(u)$ having rank $6$.

In fact, observe that imposing

$\frac{-64(1+t)^{2}(-4+7t)(4+17t)}{(1+4t)^{2}}$

as the $X$-coordinate of a new point in the Elkies surface $E$ is equivalent
to the condition $-(-4+7t)(4+17t)=\hskip 4.30554pt\vbox{\hrule
height=0.6pt\hbox{\vrule height=5.59721pt,width=0.6pt\hskip 3.44444pt\vrule
width=0.6pt}\hrule height=0.6pt}$, which can be solved with

$t\mapsto\frac{4(-1+u^{2})}{(17+7u^{2})}.$

The resulting curve has rank $5$. (For a general strategy for imposing new
points which might lead to conditions equivalent to genus $0$ or $1$ curves,
see, e.g. [4].)

On the other hand, imposing

$\frac{576(-4+7t)(-8+15t)^{2}(-1324+5551t)}{49(-39+28t)^{2}}$

as the $X$-coordinate of a new point in the Elkies surface $E$ is equivalent
to the condition $(-4+7t)(-1324+5551t)=\hskip 4.30554pt\vbox{\hrule
height=0.6pt\hbox{\vrule height=5.59721pt,width=0.6pt\hskip 3.44444pt\vrule
width=0.6pt}\hrule height=0.6pt}$, which can be solved with

$t\mapsto\frac{4(-331+u^{2})}{7(-793+u^{2})}.$

The corresponding specialization also has rank $5$.

But now we observe that in both conditions

$\displaystyle-(-4+7t)(4+17t)$ $\displaystyle=\hskip 4.30554pt\vbox{\hrule
height=0.6pt\hbox{\vrule height=5.59721pt,width=0.6pt\hskip 3.44444pt\vrule
width=0.6pt}\hrule height=0.6pt}$ $\displaystyle(-4+7t)(-1324+5551t)$
$\displaystyle=\hskip 4.30554pt\vbox{\hrule height=0.6pt\hbox{\vrule
height=5.59721pt,width=0.6pt\hskip 3.44444pt\vrule width=0.6pt}\hrule
height=0.6pt},$

the same factor $(-4+7t)$ appears. This implies that both conditions can be
satisfied simultaneously since when we apply the solution of the first
condition to the second, we have to solve $-(-1863+539u^{2})=z^{2}$ in order
to satisfy both conditions. But this genus $0$ curve has rational points, i.e.
$(u,z)=(13/7,2)$, so we can find the parametric solution

$u\mapsto\frac{-7007-28r+13r^{2}}{7(539+r^{2})}.$

So we can satisfy both conditions with

$t\mapsto\frac{4\left(3r^{2}-14r-5390\right)\left(10r^{2}-14r-1617\right)}{7\left(72r^{4}-182r^{3}-13279r^{2}+98098r+20917512\right)}.$

By inserting this into $E$, we get the curve over $\mathbb{Q}(r)$ given by

$y^{2}=x^{3}+a_{6}(r)x^{2}+b_{6}(r)x,$

where

$\displaystyle a_{6}(r)$
$\displaystyle=3(6637977907200r^{16}-327957190299648r^{15}-132939477324670464r^{14}+$
$\displaystyle 1334557851651990784r^{13}+73205200037549219248r^{12}-$
$\displaystyle 1718125119359074284768r^{11}-193538301177692188691736r^{10}+$
$\displaystyle
1905189555626165277886872r^{9}+96624855648992854220247819r^{8}-$
$\displaystyle
1026897170482503084781024008r^{7}-56226940796444312350911834456r^{6}+$
$\displaystyle
269042619584910197333660344992r^{5}+6178698341397939354226782536368r^{4}-$
$\displaystyle
60712935351132451806093801142016r^{3}-3259766993714464579957766495983104r^{2}+$
$\displaystyle
4334495070152077221968455683796992r+47287453161693896431461711200563200),$
$\displaystyle b_{6}(r)$
$\displaystyle=7225344(r-224)^{2}(r+154)^{2}(2r-7)^{2}(32r+77)^{2}\left(18r^{2}+14r+16709\right)^{2}$
$\displaystyle\left(24r^{2}-1001r+14014\right)^{2}\left(26r^{2}+1001r+12936\right)^{2}\left(31r^{2}-14r+9702\right)^{2}$
$\displaystyle\left(72r^{4}-182r^{3}-13279r^{2}+98098r+20917512\right)^{2}.$

The $x$-coordinates of six independent points of infinite order are

$\displaystyle x_{1}$
$\displaystyle=-53067(r-224)(r+154)(2r-7)(32r+77)(24r^{2}-1001r+14014)\times$
$\displaystyle(26r^{2}+1001r+12936)(72r^{4}-182r^{3}-13279r^{2}+98098r+20917512)^{2},$
$\displaystyle x_{2}$
$\displaystyle=-48(r-224)(r+154)(2r-7)(32r+77)(18r^{2}+14r+16709)\times$
$\displaystyle(31r^{2}-14r+9702)(2424r^{4}-12922r^{3}-3840473r^{2}+6964958r+704222904)^{2},$
$\displaystyle x_{3}$
$\displaystyle=144(16709+14r+18r^{2})(14014-1001r+24r^{2})(12936+1001r+26r^{2})\times$
$\displaystyle(9702-14r+31r^{2})(155719256-490490r+1032283r^{2}+910r^{3}+536r^{4})^{2},$
$\displaystyle x_{4}$
$\displaystyle=576(16709+14r+18r^{2})(14014-1001r+24r^{2})(12936+1001r+26r^{2})\times$
$\displaystyle(9702-14r+31r^{2})(434619416+2648646r-841477r^{2}-4914r^{3}+1496r^{4})^{2},$
$\displaystyle x_{5}$
$\displaystyle=(12936+1001r+26r^{2})^{2}(20917512+98098r-13279r^{2}-182r^{3}+72r^{4})^{2}\times$
$\displaystyle\frac{88510464(539+r^{2})^{2}(-7007-28r+13r^{2})^{2}(14014-1001r+24r^{2})^{2}}{(285872664+2256254r-1029833r^{2}-4186r^{3}+984r^{4})^{2}},$
$\displaystyle x_{6}$
$\displaystyle=(9702-14r+31r^{2})^{2}(20917512+98098r-13279r^{2}-182r^{3}+72r^{4})^{2}\times$
$\displaystyle\frac{260112384(539+r^{2})^{2}(-539+1001r+r^{2})^{2}(16709+14r+18r^{2})^{2}}{(676332888+2256254r+418999r^{2}-4186r^{3}+2328r^{4})^{2}}.$

Since the specification map is a homomorphism, to show that these six points
are independent, it suffices to find a rational number $r$ for which the
points are specialized to six independent $\mathbb{Q}$-rational points. It is
easy to check that we may take, e.g. $r=1$.

Moreover, for $r=13$, the conditions of the Gusić-Tadić algorithm for finding
injective specializations (see [9, Theorem 1.3] and [8]) are satisfied, so the
rank over $\mathbb{Q}(r)$ is exactly $6$.

This specialization also indicates that the points
$P_{1},P_{2},P_{3},P_{4},P_{5},P_{6}$, where $x(P_{i})=X_{i}$ for
$i=1,2,\ldots,6$, do not generate the full Mordell-Weil group over
$\mathbb{Q}(r)$ modulo torsion, but a subgroup of order $4$ (since the
quotient of the corresponding regulators is $16$). Indeed, it holds that
$P_{3}+P_{4}+P_{5}=2R_{5}$ and $P_{3}+P_{4}+P_{6}=2R_{6}$, where

$\displaystyle x(R_{5})$
$\displaystyle=1344(72r^{4}-182r^{3}-13279r^{2}+98098r+20917512)(2r-7)^{2}(32r+77)^{2}\times$
$\displaystyle(18r^{2}+14r+16709)^{2}(11r^{2}+14r+12936)^{2},$ $\displaystyle
x(R_{6})$
$\displaystyle=1344(18r^{2}+14r+16709)(26r^{2}+1001r+12936)(31r^{2}-14r+9702)\times$
$\displaystyle(24r^{2}-1001r+14014)(72r^{4}-182r^{3}-13279r^{2}+98098r+20917512)\times$
$\displaystyle\frac{(r+154)^{2}(32r+77)^{2}(6r^{2}-91r+3332)^{2}}{(30r^{2}-1001r+17248)^{2}},$

and now the points $P_{1},P_{2},P_{3},P_{4},R_{5},R_{6}$ generate the full
Mordell-Weil group over $\mathbb{Q}(r)$ modulo torsion.

##  5\. Concluding remarks

Let us mention that the heuristic of Park, Poonen, Voight and Wood (see [17,
Section 8.3]) predicts that there are only finitely many elliptic curves over
$\mathbb{Q}$ with torsion group $\mathbb{Z}/4\mathbb{Z}$ and rank greater than
$7$, which indicates that our result might be close to the best possible.

However, the recent paper by Dujella, Kazalicki and Peral [3] might indicate
that the heuristic in [17] needs some adjustments, at least in the case of
curves with certain torsion groups. Namely, they examined families with rank
$3$ for torsion groups $\mathbb{Z}/8\mathbb{Z}$ and
$\mathbb{Z}/2\mathbb{Z}\times\mathbb{Z}/6\mathbb{Z}$ and the experiments
suggest that in these families, root numbers $1$ and $-1$ (which conjecturally
means even and odd ranks) are equidistributed, which would imply that there
are infinitely many curves with rank $\geq 4$ for these torsion groups, while
the heuristic in [17] predicts that there are only finitely many elliptic
curves over $\mathbb{Q}$ with torsion group $\mathbb{Z}/8\mathbb{Z}$ or
$\mathbb{Z}/2\mathbb{Z}\times\mathbb{Z}/6\mathbb{Z}$ and rank greater than
$3$.

Acknowledgements. A. D. acknowledges support from the QuantiXLie Center of
Excellence, a project co-financed by the Croatian Government and European
Union through the European Regional Development Fund - the Competitiveness and
Cohesion Operational Programme (Grant KK.01.1.1.01.0004).

## References

  * [1] A. Dujella, High rank elliptic curves with prescribed torsion,
http://web.math.hr/~duje/tors/tors.html.

  * [2] A. Dujella, Infinite families of elliptic curves with high rank and prescribed torsion,
http://web.math.hr/~duje/tors/generic.html.

  * [3] A. Dujella, M. Kazalicki and J. C. Peral, Elliptic curves with torsion groups $\mathbb{Z}/8\mathbb{Z}$ and $\mathbb{Z}/2\mathbb{Z}\times\mathbb{Z}/6\mathbb{Z}$, Rev. R. Acad. Cienc. Exactas Fis. Nat. Ser. A Math. RACSAM 115 (2021), Article 169, (24pp).
  * [4] A. Dujella and J. C. Peral, Elliptic curves with torsion group $\mathbb{Z}/8\mathbb{Z}$ or $\mathbb{Z}/2\mathbb{Z}\times\mathbb{Z}/6\mathbb{Z}$, in: Trends in Number Theory, Contemp. Math. 649 (2015), 47–62.
  * [5] A. Dujella and J. C. Peral, Construction of high rank elliptic curves, J. Geom. Analysis 31 (2021), 6698–6724.
  * [6] N. Elkies, Three lectures on elliptic surfaces and curves of high rank, arXiv:0709.2908 (2007)
  * [7] N. Elkies and Z. Klagsbrun, New rank records for elliptic curves having rational torsion, Proceedings of the Fourteenth Algorithmic Number Theory Symposium, Mathematical Sciences Publishers, Berkeley, 2020, pp. 233–250.
  * [8] I. Gusić and P. Tadić, A remark on the injectivity of the specialization homomorphism, Glas. Mat. Ser. III 47 (2012), 265–275.
  * [9] I. Gusić and P. Tadić, Injectivity of the specialization homomorphism of elliptic curves, J. Number Theory 148 (2015), 137–152.
  * [10] H. Inose, Defining equations of singular $K3$ surfaces and a notion of isogeny, in: Proceedings of the International Symposium on Algebraic Geometry, Kinokuniya Book Store, Tokyo, 1978, pp. 495–502.
  * [11] F. Khoshnam and D. Moody, High rank elliptic curves with torsion $\mathbb{Z}/4\mathbb{Z})$ induced by Kihara’s elliptic curves, Integers 16 (2016), Paper No. A70, 12 pp.
  * [12] S. Kihara, On the rank of elliptic curves with a rational point of order $4$, Proc. Japan Acad. Ser A Math. Sci. 80 (2004), 26–27.
  * [13] S. Kihara, On the rank of elliptic curves with a rational point of order $4$, II, Proc. Japan Acad. Ser A Math. Sci. 80 (2004), 158–159
  * [14] Z. Klagsbrun, T. Sherman and J. Weigandt, The Elkies curve has rank $28$ subject only to GRH, Math. Comp. 88 (2019), 837–846
  * [15] O. Lecacheux, Rang de courbes elliptiques dont le groupe de torsion est non trivial, Ann. Sci. Math. Quebec 28 (2004), 145–151
  * [16] B. Mazur, Modular curves and the Eisenstein ideal, Inst. Hautes Études Sci. Publ. Math. 47 (1977), 33–186.
  * [17] J. Park, B. Poonen, J. Voight and M. M. Wood, A heuristic for boundedness of ranks of elliptic curves, J. Eur. Math. Soc. (JEMS) 21 (2019), 2859–2903.
  * [18] M. Schutt and T. Shioda, Mordell-Weil Lattices, Springer, Singapore, 2019.

Eliptička krivulja nad $\mathbb{Q}(u)$ s torzijom $\mathbb{Z}/4\mathbb{Z}$ i
rangom $6$

Andrej Dujella i Juan Carlos Peral

Sažetak. U ovom radu prikazujemo konstrukciju eliptičke krivulje nad
$\mathbb{Q}(u)$ s torzijskom grupom $\mathbb{Z}/4\mathbb{Z}$ i rangom $6$.
Prethodno su bili poznati samo primjeri ranga $5$ za takve krivulje.