2 Preliminaries

For $k=1,2,3,\ldots ,$ we define a set $\mathcal {N}(k)$ to be the set of all vectors of positive integers with length k and coefficients in ascending order, that is,

$$ \begin{align*} \mathcal{N}(k)=\{ \mathbf{a}=(a_1,a_2,\ldots,a_k)\in {\mathbb N}^k : a_1\le a_2\le \cdots \le a_k\}. \end{align*} $$

Put $\mathcal {N}=\bigcup _{k=1}^{\infty }\mathcal {N}(k)$ . For two vectors $\mathbf {a}\in \mathcal {N}(k)$ and $\mathbf {b}\in \mathcal {N}(s)$ with $k\le s$ , we write

$$ \begin{align*} \mathbf{a}\preceq \mathbf{b}\quad (\mathbf{a} \prec \mathbf{b}) \end{align*} $$

if the sequence $(a_i)_{1\le i\le k}$ is a (proper) subsequence of $(b_j)_{1\le j\le s}$ , where

$$ \begin{align*} \mathbf{a}=(a_1,a_2,\ldots,a_k)\quad \text{and}\quad \mathbf{b}=(b_1,b_2,\ldots,b_s). \end{align*} $$

Given a vector $\mathbf {a}\in \mathcal {N}(k)$ and a positive integer a, we define a vector $\mathbf {a}*a$ by

$$ \begin{align*} \mathbf{a}*a=(a_1,a_2,\ldots,a_i,a,a_{i+1},a_{i+2},\ldots,a_k)\in \mathcal{N}(k+1), \end{align*} $$

where i is the maximum index satisfying $a_i\le a$ , that is, $\mathbf {a}*a$ is the vector in $\mathcal {N}(k+1)$ with coefficients $a_1,a_2,\ldots ,a_k$ and a. For $\mathbf {a}\in \mathcal {N}(k)$ and $\mathbf {b}=(b_1,b_2,\ldots ,b_s)\in \mathcal {N}(s)$ , we define $\mathbf {a}*\mathbf {b}$ to be the vector

$$ \begin{align*} \mathbf{a}*b_1*b_2*\cdots*b_s \in \mathcal{N}(k+s). \end{align*} $$

We identify $\mathcal {N}(1)$ with ${\mathbb N}$ , so that, for example, $3*7*2*5$ denotes the vector $(2,3,5,7)\in \mathcal {N}(4)$ . Let S be a set of nonnegative integers containing 0 and 1 and let n be a positive integer. For a vector $\mathbf {a}=(a_1,a_2,\ldots ,a_k)\in \mathcal {N}(k)$ , we define

$$ \begin{align*} R_S(\mathbf{a})=\{ a_1s_1+a_2s_2+\cdots+a_ks_k : s_i\in S\} \quad \text{and}\quad R^{\prime}_S(\mathbf{a})=R_S(\mathbf{a})-\{0\}. \end{align*} $$

Let $\mathcal {GP}_m$ be the set of generalised m-gonal numbers, that is,

$$ \begin{align*} \mathcal{GP}_m=\{ P_m(u) : u\in {\mathbb Z} \}. \end{align*} $$

Then an m-gonal form

$$ \begin{align*} a_1P_m(x_1)+a_2P_m(x_2)+\cdots+a_kP_m(x_k) \quad (a_1\le a_2\le \cdots \le a_k) \end{align*} $$

corresponds to the pair $(\mathcal {GP}_m,\mathbf {a})$ , where $\mathbf {a}=(a_1,a_2,\ldots ,a_k)\in \mathcal {N}(k)$ . A pair $(\mathcal {GP}_m,\mathbf {a})$ ( $\mathbf {a}\in \mathcal {N}(k)$ ) will also be called a k-ary m-gonal form. Let n be a positive integer. An m-gonal form $(\mathcal {GP}_m,\mathbf {a})$ is called $\mathcal T(n)$ -universal if $R^{\prime }_{\mathcal {GP}_m}(\mathbf {a})\supseteq \mathcal T(n)$ and tight $\mathcal T(n)$ -universal if $R^{\prime }_{\mathcal {GP}_m}(\mathbf {a})=\mathcal T(n)$ . A tight $\mathcal T(n)$ -universal m-gonal form $(\mathcal {GP}_m,\mathbf {a})$ is called new if $R^{\prime }_{\mathcal {GP}_m}(\mathbf {b})\subsetneq \mathcal T(n)$ for every vector $\mathbf {b}\in \mathcal {N}$ satisfying $\mathbf {b}\prec \mathbf {a}$ . When $n=1$ , we use the expression ‘universal’ along with ‘tight $\mathcal T(1)$ -universal’ to follow the convention.

Proof. Let $\mathbf {b}=(n,n,\ldots ,n)\in \mathcal {N}(m)$ be the vector of length m with every coefficient equal to n. By Fermat’s polygonal number theorem,

$$ \begin{align*} R_{\mathcal{GP}_m}(\mathbf{b})=\{ nu : u\in {\mathbb Z}_{\ge 0} \}. \end{align*} $$

From this, one may easily deduce that

$$ \begin{align*} R^{\prime}_{\mathcal{GP}_m}(\mathbf{b}*(n+1)*(n+2)*\cdots*(2n-1))=\mathcal T(n). \end{align*} $$

This completes the proof.

3 An algorithm for tight $\mathcal T(n)$ -universal sums of m-gonal numbers

We introduce an algorithm which gives all new tight $\mathcal T(n)$ -universal m-gonal forms. Let m be an integer $\ge 3$ and n be a positive integer. For $\mathbf {a}\in \mathcal {N}$ , we denote by $\Psi (\mathbf {a})$ the set of integers in $\mathcal T(n)$ which are not represented by the m-gonal form $(\mathcal {GP}_m,\mathbf {a})$ , that is,

$$ \begin{align*} \Psi(\mathbf{a})=\Psi_{m,n}(\mathbf{a})=\mathcal T(n)-R^{\prime}_{\mathcal{GP}_m}(\mathbf{a}). \end{align*} $$

We define a function $\psi =\psi _{m,n} : \mathcal {N}\to \mathcal T(n)\cup \{ \infty \}$ by

$$ \begin{align*} \psi(\mathbf{a})=\begin{cases}\min(\Psi(\mathbf{a}))&\text{if}\ \ \Psi(\mathbf{a})\neq \emptyset,\\ \infty&\text{otherwise.}\end{cases} \end{align*} $$

For a vector $\mathbf {a}$ with $\psi (\mathbf {a})<\infty $ , we define the set $\mathcal E(\mathbf {a})$ by

$$ \begin{align*} \mathcal E(\mathbf{a})=\{ g\in {\mathbb Z} : n\le g\le \psi(\mathbf{a})-n\} \cup \{ \psi(\mathbf{a})\}. \end{align*} $$

Note that if $\psi (\mathbf {a})<2n$ , then $\mathcal E(\mathbf {a})=\{ \psi (\mathbf {a})\}$ . For $k=1,2,3,\ldots ,$ we define subsets $E(k),U(k),\mathit {NU}(k)$ and $A(k)$ of $\mathcal {N}(k)$ recursively as follows. Put $E(1)=\{(n)\}$ . Define

$$ \begin{align*} U(k)=\{ \mathbf{a}\in E(k) : \psi(\mathbf{a})=\infty \}. \end{align*} $$

Let $\mathit {NU}(k)$ be the set of all vectors $\mathbf {a}$ in $U(k)$ such that $\mathbf {b}\not \in \bigcup _{i=1}^{k-1}U(i)$ for every $\mathbf {b}\in \mathcal {N}$ satisfying $\mathbf {b}\prec \mathbf {a}$ . Let $A(k)=E(k)-U(k)$ and

$$ \begin{align*} E(k+1)=\bigcup_{\mathbf{a}\in A(k)}\{ \mathbf{a}*g : g\in \mathcal E(\mathbf{a})\}. \end{align*} $$

The algorithm terminates once $A(k)=\emptyset $ .

Proof. The ‘if’ part is clear by construction. To prove the ‘only if’ part, let $\mathbf {a}\in \mathcal {N}(k)$ be a vector such that $(\mathcal {GP}_m,\mathbf {a})$ is tight $\mathcal T(n)$ -universal. Since $R^{\prime }_{\mathcal {GP}_m}(\mathbf {a})=\mathcal T(n)$ , it clearly follows that $a_{i_1}=n$ , where we put $i_1=1$ . Note that the set $R_{\mathcal {GP}_m}(a_{i_1})$ does not contain any positive integer less than n and it does contain 0 and all integers from n to ${\psi (a_{i_1})-1}$ . From this and $\psi (a_{i_1})\in \mathcal T(n)=R^{\prime }_{\mathcal {GP}_m}(\mathbf {a})$ , one may easily deduce that there must be an index $i_2$ different from $i_1$ such that

$$ \begin{align*} a_{i_2}\in \mathcal E(a_{i_1})=\{ n,n+1,n+2,\ldots,\psi(a_{i_1})-n\} \cup \{\psi(a_{i_1})\}. \end{align*} $$

Thus $a_{i_1}*a_{i_2}\preceq \mathbf {a}$ , where $a_{i_1}*a_{i_2}\in E(2)$ . Note that $\psi (a_{i_1})\in R^{\prime }_{\mathcal {GP}_m}(a_{i_1}*a_{i_2})$ . Assume $R^{\prime }_{\mathcal {GP}_m}(a_{i_1}*a_{i_2})\subsetneq \mathcal T(n)$ so that $\psi (a_{i_1}*a_{i_2})<\infty $ . One may easily show that there should be an index $i_3$ different from both $i_1$ and $i_2$ such that

$$ \begin{align*} a_{i_3}\in \mathcal E(a_{i_1}*a_{i_2})=\{ n,n+1,n+2,\ldots,\psi(a_{i_1}*a_{i_2})-n\} \cup \{ \psi(a_{i_1}*a_{i_2})\} \end{align*} $$

in a similar manner. We have $a_{i_1}*a_{i_2}*a_{i_3}\in E(3)$ by construction. Note that

$$ \begin{align*} \psi(a_{i_1}*a_{i_2}*\cdots*a_{i_j})<\infty \end{align*} $$

for every $j=1,2,\ldots ,k-1$ since otherwise, $(\mathcal {GP}_m,\mathbf {a})$ cannot be new. Repeating this, we arrive at

$$ \begin{align*} \mathbf{a}=a_{i_1}*a_{i_2}*\cdots*a_{i_k}\in E(k). \end{align*} $$

Since $(\mathcal {GP}_m,\mathbf {a})$ is new tight $\mathcal T(n)$ -universal, one may easily see that $\mathbf {a}\in \mathit {NU}(k)$ . This completes the proof.

Although the proof of the following lemma appeared in the proof of [Reference Kane and Liu9, Lemma 2.1], we provide it for completeness. For two positive integers d and r, we define a set

$$ \begin{align*} \mathcal {AP}_{d,r}=\{dg+r : g\in {\mathbb N} \cup \{0\} \} \ (\subseteq {\mathbb N}). \end{align*} $$

Proof. Let t be a positive integer greater than 4 and let $\mathbf {a}=(a_1,a_2,\ldots ,a_t)$ be a vector in $A(t)=E(t)-U(t)$ so that $\psi (\mathbf {a})<\infty $ . Note that, for any ${\mathbb Z}$ -lattice L of rank $\ge 4$ with $Q(\text {gen}(L))\subsetneq {\mathbb N}$ ,

$$ \begin{align*} {\mathbb N}-Q(\text{gen}(L))=\bigcup_{i=1}^{\nu^{\prime}_1} \mathcal {AP}_{d^{\prime}_i,r^{\prime}_i} \end{align*} $$

for some positive integers $\nu ^{\prime }_1,d^{\prime }_i$ and $r^{\prime }_i$ with $r^{\prime }_i<d^{\prime }_i$ by the results in [Reference O’Meara14]. From this and [Reference Chan, Oh, Chan and Schulze-Pillot3, Theorem 4.9] (see also [Reference Hsia, Kitaoka and Kneser5]), one may easily deduce that

$$ \begin{align*} \mathcal T(n)-R^{\prime}_{\mathcal{GP}_m}(\mathbf{a})=\bigcup_{i=1}^{\nu_1} \mathcal {AP}_{d_i,r_i} \cup \{ e_1,e_2,\ldots,e_{\nu_2}\} \end{align*} $$

for some nonnegative integers $\nu _1,\nu _2$ not both 0 and some positive integers $d_i,r_i,e_j$ with $e_j\not \in \bigcup _{i=1}^{\nu _1} \mathcal {AP}_{d_i,r_i}$ for all $j=1,2,\ldots ,\nu _2$ . Suppose that $g_1$ is a positive integer with $n\le g_1\le \psi (\mathbf {a})-n$ or $g_1=\psi (\mathbf {a})$ so that $\mathbf {a}*g_1\in E(t+1)$ . If

$$ \begin{align*} Q(\text{gen}(\langle a_1,a_2,\ldots,a_t\rangle))\subsetneq Q(\text{gen}(\langle a_1,a_2,\ldots,a_t,g_1\rangle)), \end{align*} $$

then

$$ \begin{align*} \mathcal T(n)-R^{\prime}_{\mathcal{GP}_m}(\mathbf{a}*g_1)=\bigcup_{w=1}^{\nu_3} \mathcal {AP}_{d_{i_w},r_{i_w}} \cup \{ e^{\prime}_1,e^{\prime}_2,\ldots,e^{\prime}_{\nu_4}\}, \end{align*} $$

where $\nu _3$ is an integer with

$$ \begin{align*} 0\le \nu_3<\nu_1,\quad (i_1,i_2,\ldots,i_{\nu_3})\prec (1,2,\ldots,\nu_1), \end{align*} $$

and $\nu _4$ is a nonnegative integer. When

$$ \begin{align*} Q(\text{gen}(\langle a_1,a_2,\ldots,a_t\rangle))=Q(\text{gen}(\langle a_1,a_2,\ldots,a_t,g_1\rangle)), \end{align*} $$

it follows that

$$ \begin{align*} \mathcal T(n)-R^{\prime}_{\mathcal{GP}_m}(\mathbf{a}*g_1)=\bigcup_{i=1}^{\nu_1} \mathcal {AP}_{d_i,r_i} \cup \{ e_{j_1},e_{j_2},\ldots,e_{j_{\nu_5}}\}, \end{align*} $$

where $\nu _5$ is a nonnegative integer less than $\nu _2$ and $(j_1,j_2,\ldots ,j_{\nu _5})\prec (1,2,\ldots ,\nu _2)$ .

Let $\mathbf {b}$ be a vector in $A(5)=E(5)-U(5)$ . From what we observed above, we may define a positive integer $w=w(\mathbf {b})$ to be the maximal positive integer w satisfying

$$ \begin{align*} b*g_1*g_2*\cdots*g_i\in A(5+i)-U(5+i),\quad g_i\in \mathcal E(b*g_1*g_2*\cdots*g_{i-1}), \end{align*} $$

for every $i=1,2,\ldots ,w-1$ . Since the set $E(5)$ is finite by construction, we may take l as

$$ \begin{align*} l=5+\max \{w(\mathbf{b}) : \mathbf{b}\in E(5)-U(5)\}. \end{align*} $$

This completes the proof.

We now introduce our main result which gives a natural generalisation of the Conway–Schneeberger 15-Theorem to the case of tight $\mathcal T(n)$ -universal m-gonal forms.

Proof. Using Lemma 3.2, we take the smallest positive integer l satisfying $A(l)=\emptyset $ . Define a finite set

$$ \begin{align*} CS(m,n)=\{n\} \cup \bigcup_{k=1}^{l-1}\{ \psi(\mathbf{a}) : \mathbf{a}\in A(k)\}. \end{align*} $$

Let $\mathbf {a}\in \mathcal {N}$ be a vector with $R^{\prime }_{\mathcal {GP}_m}(\mathbf {a})\cap \{1,2,\ldots ,n-1\}=\emptyset $ such that $R^{\prime }_{\mathcal {GP}_m}(\mathbf {a})\supset CS(m,n)$ . From the condition that $R^{\prime }_{\mathcal {GP}_m}(\mathbf {a})\supset CS(m,n)$ , one may easily see that there is a vector $\mathbf {b}\in \mathcal {N}$ with $\mathbf {b}\preceq \mathbf {a}$ such that $\mathbf {b}\in U(k)$ for some k less than or equal to $l$ . It follows that

$$ \begin{align*} \mathcal T(n)=R^{\prime}_{\mathcal{GP}_m}(\mathbf{b})\subseteq R^{\prime}_{\mathcal{GP}_m}(\mathbf{a}). \end{align*} $$

This completes the proof.

In the spirit of Remark 3.4 and [Reference Kim, Lee and Oh11], we may call the set $CS(m,n)$ a minimal tight $\mathcal T(n)$ -universality criterion set for m-gonal forms.

Proof. Note that $2\not \in \mathcal {GP}_m$ since $m\neq 5$ . For $i=1,2,\ldots ,n-1$ , one may easily show that $\psi (n)=n+1$ and

$$ \begin{align*} \psi(n,n+1,n+2,\ldots,n+i)=n+i+1. \end{align*} $$

The proposition follows directly from this.

Remark 3.6. Proposition 3.5(i), (ii) and (iii) also hold for the case of pentagonal forms, that is, when $m=5$ . However, Proposition 3.5(iv) is no longer true when $m=5$ . In fact, since $2=P_5(-1)\in \mathcal {GP}_5$ , we have

$$ \begin{align*} 2n\in R^{\prime}_{\mathcal{GP}_5}(n)\subset R^{\prime}_{\mathcal{GP}_5}(n,n+1,n+2,\ldots,2n-1), \end{align*} $$

and thus we would have $\psi (n,n+1,n+2,\ldots ,2n-1)>2n$ .

4 Some experimental results

We provide some experimental results based on the escalation algorithm for tight $\mathcal T(n)$ -universal m-gonal forms introduced in Section 3. We first note that, in practice, we use the set

$$ \begin{align*} \Psi(\mathbf{a})=\Psi_{m,n}(\mathbf{a})=\{ u \in \mathcal T(n) : u\le 10^6 \}-R^{\prime}_{\mathcal{GP}_m}(\mathbf{a}) \end{align*} $$

instead of the original definition $\Psi (\mathbf {a})=\mathcal T(n)-R^{\prime }_{\mathcal {GP}_m}(\mathbf {a})$ in the algorithm so that

$$ \begin{align*} \{ u\in {\mathbb N} : n\le u\le 10^6\} \subset R^{\prime}_{\mathcal{GP}_m}(\mathbf{a})\quad\mbox{for all } \mathbf{a}\in \bigcup_{k=1}^{\infty} U(k). \end{align*} $$

In Table 1, we give the sets $CS(m,n)$ for some pairs $(m,n)$ . In the table, the pair $(m,n)$ is marked with $\dagger $ when the tight $\mathcal T(n)$ -universal m-gonal forms are already completely classified so that the set $CS(m,n)$ in the table has been proved to be equal to the set $CS(m,n)$ in the algorithm in Section 3.

Table 1

$CS(m,n)$ for some pairs $(m,n)$ .

For the classification of tight $\mathcal T(n)$ -universal m-gonal forms, we refer the reader to [Reference Bhargava1] for $(m,n)=(4,1)$ , [Reference Bosma and Kane2] for $(m,n)=(3,1)$ , [Reference Ju and Oh8] for $(m,n)=(8,1)$ , [Reference Ju6] for $(m,n)=(5,1)$ , [Reference Kim and Oh13] for $m=4$ and $n\ge 2$ , and [Reference Kim12] for the others. The tight universal m-gonal forms are classified for $m=4,3$ , and tight $\mathcal T(n)$ -universal octagonal forms for all $n\ge 2$ are treated in [Reference Ju and Kim7]. In this spirit, we provide the candidates for tight $\mathcal T(n)$ -universal pentagonal forms in the cases of $n=2,3$ in Tables 2 and 3, respectively. Note that there is exactly one candidate for tight $\mathcal T(n)$ -universal pentagonal forms for each $n=4,5,6$ , which is $(\mathcal {GP}_5,(n,n+1,n+2,\ldots ,2n-1))$ .

Table 2

Candidates for new tight $\mathcal T(2)$ -universal pentagonal forms $(\mathcal {GP}_5,(a_1,a_2,\ldots ,a_k))$ .

Table 3

Candidates for new tight $\mathcal T(3)$ -universal pentagonal forms $(\mathcal {GP}_5,(a_1,a_2,\ldots ,a_k))$ .

For any integer $m\ge 3$ and a positive integer n, we define $\gamma _{m,n}$ to be the maximum element in the set $CS(m,n)$ , as in the proof of Theorem 3.3. By Theorem 3.3, if an m-gonal form g does not represent any integer less than n and does represent all integers from n to $\gamma _{m,n}$ , then g is tight $\mathcal T(n)$ -universal. For $m=3,4,\ldots ,$ we define

$$ \begin{align*} \gamma_m=\gamma_{m,1}=\max(C(m,1)). \end{align*} $$

Now we consider universal m-gonal forms. In Table 4, $\gamma _m$ is given for $3\le m\le 11$ and the proved cases are marked $\dagger $ . We provide all candidates of new universal m-gonal forms, for $m=7,9,10,11$ , in Tables 5–8, since the universal m-gonal forms are of particular interest.

Table 4

$\gamma _m$ for $3\le m\le 11$ .

Table 5

Candidates for new universal heptagonal forms $(\mathcal {GP}_7,(a_1,a_2,\ldots ,a_k))$ .

Table 6

Candidates for new universal nonagonal forms $(\mathcal {GP}_9,(a_1,a_2,\ldots ,a_k))$ .

Table 7

Candidates for new universal decagonal forms $(\mathcal {GP}_{10},(a_1,a_2,\ldots ,a_k))$ .

Table 8

Candidates for new universal hendecagonal forms $(\mathcal {GP}_{11},(a_1,a_2,\ldots ,a_k))$ .