, 2022

Let $N = \binom{n}{3}$. Let's first show that the statement holds for $t \le \binom{N+3}{2}$ and all good functions of order at most $N+1$. This can be proved by induction on $N$. It is trivial when $N=0$. Now suppose that the statement holds for all smaller $N$, then for any good function with $N$ multiplications, if there is no $\text{gcd}$ in the expression, then the statement is also trivial. Therefore we now also assume that the statement is true for all good functions with $N$ multiplications and fewer numbers of $\text{gcd}$'s. Note that a nontrivial (i.e. not $a$ nor $b$) good function is of the form
$$\text{gcd}(f(a, b), g(a, b))$$
or
$$f(a, b)g(a, b).$$
In the former case, the statement clearly holds by the inductive hypothesis. For the latter, suppose that there are $q$ multiplications in $f(a, b)$ and $r$ in $g(a, b)$. Then $q+r = N-1$, and by the inductive hypothesis there are good functions $Q_1(a, b), \dots, Q_u(a, b)$ of order at most $q+1$ and good functions $R_1(a, b), \dots, R_v(a, b)$ of order at most $r+1$ such that our target function looks like
$$\text{gcd}(Q_1(a, b), \dots, Q_u(a, b)) \cdot \text{gcd}(R_1(a, b), \dots, R_v(a, b)).$$
Since $\gcd(x, y) \gcd(z, w) = \gcd(xz, xw, yz, yw)$, we can write the right hand side as
$$\gcd\{Q_i(a, b)R_j(a, b) \mid i = 1, \dots, u, \ j = 1, \dots, v\}.$$
Note that $Q_i R_j$ is a good function of order at most $(q+1) + (r+1) = N+1$. After getting rid of the repeated good functions, we have proven the desired statement via induction.

Now note that if $(x_1, y_1) \le (x_2, y_2)$, then $a^{x_1} b^{y_1}$ divides $a^{x_2} b^{y_2}$, showing that $\gcd(a^{x_1} b^{y_1}, a^{x_2} b^{y_2}) = a^{x_1} b^{y_1}$. Moreover, if $(x_1, y_1), (x_2, y_2), (x_3, y_3) \in \mathbb{Z}_{\ge 0}^2$ are such that $(x_3, y_3)$ is above the segment connecting $(x_1, y_1), (x_2, y_2)$, then clearly $\gcd(a^{x_1} b^{y_1}, a^{x_2} b^{y_2})$ always divides $a^{x_3} b^{y_3}$ by an easy $p$-adic analysis. Thus, we can reduce $\gcd(a^{x_1} b^{y_1}, a^{x_2} b^{y_2}, a^{x_3} b^{y_3})$ to $\gcd(a^{x_1} b^{y_1}, a^{x_2} b^{y_2})$. We can use these to reduce the formula, and suppose that at last we have the good function
$$\gcd(a^{x_1} b^{y_1}, \dots, a^{x_t} b^{y_t})$$
with $x_1 < \dots < x_t$ (note that equality cannot occur, for otherwise the expression can be further reduced). Since the expression is not reducible, we have that $y_1 > y_2 > \dots > y_t$. Moreover, we know that
$$\frac{y_1 - y_2}{x_2 - x_1} > \frac{y_2 - y_3}{x_3 - x_2} > \dots > \frac{y_{t-1} - y_t}{x_t - x_{t-1}}$$
Hence, if $t > \binom{n}{2}$, then
$$\begin{aligned} 2\binom{n}{3} + 2 &\ge (x_t - x_1) + (y_1 - y_t) \\ &= \sum_{i=1}^{t-1} (x_{i+1} - x_i) + (y_i - y_{i+1}) \\ &\ge 2\binom{n}{3} + \left(t - \binom{n}{2}\right)n \\ &\ge 2\binom{n}{3} + n, \end{aligned}$$
which is a contradiction.