Denote the set of all positive integers by $\mathbb{N}$, and the set of all ordered positive integers by $\mathbb{N}^2$. For all non-negative integers $k$, define good functions of order k recursively for all non-negative integers $k$, among all functions from $\mathbb{N}^2$ to $\mathbb{N}$ as follows: (i) The functions $f(a,b)=a$ and $f(a,b)=b$ are both good functions of order $0$. (ii) If $f(a,b)$ and $g(a,b)$ are good functions of orders $p$ and $q$, respectively, then $\gcd(f(a,b),g(a,b))$ is a good function of order $p+q$, while $f(a,b)g(a,b)$ is a good function of order $p+q+1$. Prove that, if $f(a,b)$ is a good function of order $k\leq \binom{n}{3}$ for some positive integer $n\geq 3$, then there exist a positive integer $t\leq \binom{n}{2}$ and $t$ pairs of non-negative integers $(x_1,y_1),\ldots,(x_n,y_n)$ such that $$f(a,b)=\gcd(a^{x_1}b^{y_1},\ldots,a^{x_t}b^{y_t})$$holds for all positive integers $a$ and $b$. Proposed by usjl
Problem
Source: 2022 Taiwan TST Round 3 Independent Study 1-N
Tags: number theory, greatest common divisor, function, Taiwan
27.04.2022 08:22
Who would have thought that in this contest, the longer the problem the easier it is... The main idea seems to be that points in S must be a lower convex hull
15.11.2022 07:30
I think the "Good order of function" is not well defined. for example $f(a,b)=a$ has good order 0 and $b$ has good order 0 so $ab$ has good order $0+0+1=1$ then $a=(a,ab)$ has good order $0+1=1$ so $f(a,b)=a$ has good order 0 and 1 at the same time. Another problem is that how to define $gcd(a,b)gcd(c,d)$ ? Is it $gcd(ac,ad,bc,bd)$?
15.11.2022 08:33
What's wrong with a function being of good order 0 and 1? Also the product of two gcd's is defined as... the product of two gcd's. You could show that it is equal to the gcd of the four products if you like. I don't really see what is confusing.
15.11.2022 09:27
sorry I didn't realize that one function can have many good orders...
25.02.2023 17:14
This is a really nice problem. For a function $f$, let $S_{f}$ be the set of minimal size $\{ (x_1,y_1),\ldots,(x_m,y_m) \}$ where $x_{1} < x_{2} < \dots < x_{m}$ and $f(a,b)=\gcd(a^{x_1}b^{y_1},\ldots,a^{x_t}b^{y_t})$. Verify with easy induction that if $f$ is a function with order $k$ then for all $(x_{i}, y_{i}) \in S_{f},$ $x_{i} + y_{i} \le k+1.$ Consider a function $f(a,b)$ with order $k \le \binom{n}{3}$. Note that $y_{1} < y_{2} < \dots y_{m}$ because $a^{x_i}b^{y_i} \nmid a^{x_j} b^{y_j}$ for any $ i \ne j.$ Furthermore, $(x_{i}, y_{i}) \in S_f$ form a "convex curve", in other words for $a < b < c$ then $(x_{b}, y_{b})$ lies strictly under the segment joining $(x_{a}, y_{a})$ and $(x_{c}, y_{c}).$ Combining these, we can see the slopes $$(x_{1}, y_{1})-(x_{2}, y_{2}), (x_{2}, y_{2})-(x_{3}, y_{3}), \cdots ,(x_{m-1}, y_{m-1})-(x_{m}, y_{m}),$$are strictly increasing (strictly decreasing in terms of magnitude). Let the magnitudes of these slopes be $\frac{a_{1}}{b_{1}}, \frac{a_{2}}{b_{2}}, \dots \frac{a_{m-1}}{b_{m-1}}$ for positive integers $a_{1}, \dots a_{m-1}, b_{1}, \dots b_{m-1}$. Then it is clear that $a_{1} + \dots + a_{m-1} + b_{1} + \dots + b_{m-1} \le 2k.$ But for a given positive integer $i$ there are at most $i-1$ slopes $\frac{a}{b}$ where $a,b$ are positive integers and $a+b = i.$ So observe that if $m > \binom{n}{2}$ then \begin{align*} a_{1} + \dots + a_{m-1} + b_{1} + \dots + b_{m-1} &\ge 2 \cdot 1 + 3 \cdot 2 + \dots + n \cdot (n-1) \\ &\ge 2 \left( \binom{2}{2} + \binom{3}{2} + \dots + \binom{n}{2} \right) \\ &\ge 2 \binom{n+1}{3} \\ &> 2 \left( \binom{n}{3} + 1 \right) \\ &> 2k \end{align*}which is contradiction. $\blacksquare$