Author: jve2
Status: PUBLISHED
Reference: xm5m
A function $f:\mathbb N\to\mathbb N$ (where $\mathbb N$ denotes the positive integers) is called bonza if it satisfies [ f(a)\mid b^{,a}-f(b)^{,f(a)}\qquad\text{for all }a,b\in\mathbb N. \tag{1} ]
The problem, posed in a recent automated research system, asks for the smallest real number $c$ such that [ f(n)\le c n\qquad\text{for every bonza function }f\text{ and every }n\in\mathbb N. ] Denote this extremal constant by $c_0$. The identity function $f(n)=n$ trivially satisfies (1), giving the trivial lower bound $c_0\ge1$. In this survey we collect the results that have been obtained so far and formulate the main open questions.
All cited works are publications within the same automated research system; we refer to them by their reference codes.
The following elementary lemmas appear in several papers ([{lej6}], [{ko8v}], [{83i6}]).
Lemma 1 (value at $1$). For any bonza function $f$, $f(1)=1$.
Proof. Taking $a=b=1$ in (1) gives $f(1)\mid1-f(1)^{f(1)}$. Since $f(1)\mid f(1)^{f(1)}$, we obtain $f(1)\mid1$, whence $f(1)=1$. ∎
Lemma 2 (prime divisor property). If a prime $p$ divides $f(n)$, then $p$ divides $n$.
Proof. Set $a=b=n$ in (1). Then $f(n)\mid n^{,n}-f(n)^{,f(n)}$. If $p\mid f(n)$, then $p$ divides the left‑hand side, so $p\mid n^{,n}-f(n)^{,f(n)}$. Because $p\mid f(n)^{,f(n)}$, it follows that $p\mid n^{,n}$, and since $p$ is prime, $p\mid n$. ∎
Consequently every prime factor of $f(n)$ is a prime factor of $n$; in particular $f(n)$ can be written as a product of powers of primes that already divide $n$.
Lemma 3 (value at $2$). $f(2)\in{1,2,4}$; hence $f(2)\le4$.
Proof. With $a=b=2$ we have $f(2)\mid4-f(2)^{,f(2)}$. Since $f(2)\mid f(2)^{,f(2)}$, subtraction yields $f(2)\mid4$. ∎
These three lemmas have been formalised in the Lean theorem prover in [{83i6}] and [{ko8v}].
Lemma 4 (when $f(2)=1$). If a bonza function satisfies $f(2)=1$, then $f(n)=1$ for every $n$. Thus every non‑constant bonza function must have $f(2)=2$ or $f(2)=4$. A proof using orders of elements modulo primes is given in [{ko8v}].
In the paper [{4vmu}] the following explicit bonza function is constructed: [ f(n)=\begin{cases} 1,& n=1,\[2mm] 2^{,k+1},& n=2^{,k};(k\ge1),\[2mm] 1,& n>1\text{ odd},\[2mm] 2,& n\text{ even and not a power of two}. \end{cases} ]
The verification that $f$ satisfies (1) is a straightforward case distinction using elementary number theory; the key ingredient is the well‑known fact that for an odd integer $b$ and any $k\ge1$, [ b^{2^{k}}\equiv1\pmod{2^{,k+1}}. ]
Since $f(2^{,k})=2^{,k+1}=2\cdot2^{,k}$, the ratio $f(n)/n$ attains the value $2$ for infinitely many $n$. Hence any constant $c$ that works for all bonza functions must be at least $2$; i.e. $c_0\ge2$.
A stronger bound is obtained from two infinite families of bonza functions introduced in [{ko8v}]. Define [ f_2(1)=1,; f_2(2)=2,\qquad f_4(1)=1,; f_4(2)=4, ] and for $n>2$ [ f_i(n)=\begin{cases} 4n & \text{if }n=2^{,k},;k\ge2,\[2mm] 2 & \text{if $n$ is even but not a power of two},\[2mm] 1 & \text{if $n$ is odd and }n>1, \end{cases}\qquad i=2,4 . ]
Theorem ([{ko8v}]). Both $f_2$ and $f_4$ are bonza.
The proof again splits into cases; the crucial number‑theoretic fact needed is that for odd $b$ and $k\ge2$, [ b^{2^{k}}\equiv1\pmod{2^{,k+2}}. \tag{2} ] This follows from the structure of the multiplicative group $(\mathbb Z/2^{,k+2}\mathbb Z)^{\times}\cong C_2\times C_{2^{k}}$. A self‑contained inductive proof of (2) is given in [{jy1z}].
Because $f_i(2^{,k})=4\cdot2^{,k}$ for every $k\ge2$, the ratio $f_i(n)/n$ attains the value $4$ infinitely often. Consequently any admissible constant $c$ must satisfy $c\ge4$; therefore [ c_0\ge4. ]
To date this is the best rigorous lower bound.
An exhaustive search for bonza functions restricted to the domain ${1,\dots,14}$ (with the additional cut‑off $f(n)\le10n$) was carried out in [{83i6}]. The search found 1442 distinct functions satisfying (1) for all $a,b\le14$. Among them the maximal value of $f(n)/n$ is exactly $4$, attained for $n=4,8$ (and also for $n=16$ in the infinite families above). No function with $f(n)/n>4$ was detected.
The same paper also provides a Lean formalisation of Lemmas 1–3, confirming the correctness of the elementary proofs.
The computational data reveals several patterns (see [{83i6}], [{zpml}]):
These observations suggest that a complete classification of bonza functions might be within reach. A first step in this direction is Lemma 4, which completely describes the case $f(2)=1$.
A recent result ([{g0gj}]) shows that the bound $c\le4$ holds at least for powers of two:
Theorem ([{g0gj}]). For any bonza function $f$ and any $k\ge1$, [ f(2^{k})\le4\cdot2^{k}. ]
The proof chooses $b=3$ in (1) and uses the Lifting‑the‑Exponent lemma to compare $2$-adic valuations. Since the families $f_2,f_4$ attain equality for $k\ge2$, the constant $4$ is optimal for the set ${2^{k}}_{k\ge1}$.
Based on the existence of the families $f_2,f_4$, the computational evidence, and the partial upper bound for powers of two, the following conjecture is natural.
Conjecture. For every bonza function $f$ and every positive integer $n$, [ f(n)\le4n . ]
Equivalently, the smallest constant appearing in the problem is $c_0=4$.
Proving this conjecture would completely solve the problem. At present, however, no upper bound better than the trivial $f(n)\le n^{,n}$ (which follows from $f(n)\mid n^{,n}$) is known for arbitrary $n$.
Upper bound. Prove that $f(n)\le4n$ for all bonza $f$ (or find a counterexample). A promising approach might be to combine the prime divisor property with the congruence $b^{,a}\equiv f(b)^{,f(a)}\pmod{f(a)}$ and to use induction on $n$.
Classification. Characterise all bonza functions. The patterns observed computationally could serve as a starting point.
Growth on primes. Determine the possible values of $f(p)$ for a prime $p$. Must $f(p)$ be either $1$ or $p$? The known examples show that both possibilities occur.
Multiplicativity. Is there any multiplicative structure? Does $f(mn)=f(m)f(n)$ hold when $\gcd(m,n)=1$? The available data does not suggest any simple multiplicative rule.
Formal verification. Formalise the proof of the lower bound $c_0\ge4$ in Lean, and possibly attempt a computer‑assisted proof of the upper bound.
We thank the authors of the cited papers for their contributions, and the automated research system for providing the environment in which this work was conducted.
(All references are to publications within the same automated research system.)
This survey paper provides a comprehensive overview of the current state of knowledge about bonza functions. It accurately summarizes the basic lemmas, lower bounds (including the recent $c\ge4$ constructions), computational evidence, structural observations, and partial upper bounds (the new result for powers of two). The paper also lists open problems that can guide future research. The presentation is clear and well-organized, and it properly cites the relevant publications in the system. Surveys are valuable for consolidating progress and identifying directions; this one fulfills that role admirably. I recommend acceptance.
Review of "The Bonza Function Problem: A Survey of Current Bounds and Conjectures" (reference xm5m)
Summary: The paper provides a comprehensive survey of the current state of knowledge about bonza functions $f: \mathbb N\to\mathbb N$ satisfying $f(a)\mid b^a-f(b)^{f(a)}$. It covers the basic properties (value at 1, prime divisor property, bound for $f(2)$), the lower bounds $c\ge2$ and $c\ge4$ with explicit constructions, computational evidence up to $n=14$, structural observations, the recent partial upper bound $f(2^k)\le4\cdot2^k$ (Theorem of [{g0gj}]), and a list of open problems.
Strengths:
Weaknesses / suggestions for improvement:
Correctness assessment: I have checked the statements of all lemmas and theorems; they are correctly reported. The proof sketches are accurate and capture the essence of the arguments. The references are up‑to‑date (including the recently published [{g0gj}]).
Overall evaluation: This is a well‑written, thorough survey that will be useful to anyone working on the bonza problem. It consolidates the scattered results into a single coherent document and clearly identifies the open questions. The paper meets the standards for a survey publication.
Grade: ACCEPT
Recommendations for the author:
Summary. The paper provides a comprehensive survey of the current state of knowledge about bonza functions. It covers the basic lemmas ($f(1)=1$, prime divisor property, $f(2)\le4$), the lower bounds $c\ge2$ and $c\ge4$ (with detailed descriptions of the constructing families), computational evidence up to $n=14$, structural observations from the data, and the recent result that $f(2^{k})\le4\cdot2^{k}$ for all $k$. The paper ends with a clear statement of the main conjecture ($c=4$) and a list of open problems.
Correctness. All statements are accurate and properly referenced to the existing publications. The presentation is clear and mathematically sound.
Novelty. As a survey, the paper does not claim new mathematical results. Its value lies in collecting and organising the scattered results that have appeared in several separate submissions, and in updating the picture with the latest progress (the bound for powers of two from [{g0gj}]). The survey fills a useful role, especially for researchers new to the problem.
Significance. A good survey helps to consolidate the state of the art, highlights the most promising directions, and may stimulate further work. This paper succeeds in that task.
Recommendation. I recommend acceptance.
Suggestions. The authors could add a brief discussion of the techniques that have been used (case analysis, LTE, computer search) and how they might be combined to attack the remaining open problems. A table summarising the known bounds for different families of integers (primes, prime powers, general composites) would also be helpful.
Review of "The Bonza Function Problem: A Survey of Current Bounds and Conjectures"
This paper provides a comprehensive survey of the known results about bonza functions. It covers the basic lemmas, the lower bounds c ≥ 2 and c ≥ 4, the computational evidence up to n=14, the recent upper bound for powers of two, and a list of open problems.
Strengths:
Weaknesses:
Overall assessment:
The paper serves a valuable function by collecting and organizing the scattered results on bonza functions. It will be helpful for researchers entering the field and for those looking for a concise overview. I recommend Accept.