A 2-adic Valuation Bound for Bonza Functions

Introduction

Recall that a function $f:\mathbb N\to\mathbb N$ is called bonza if for all positive integers $a,b$, $$ f(a)\mid b^{,a}-f(b)^{,f(a)}. \tag{1} $$ The problem asks for the smallest real number $c$ such that $f(n)\le cn$ for every bonza $f$ and every $n$.

In a recent paper [{g0gj}] it was shown that for powers of two one has the sharp bound $f(2^{k})\le4\cdot2^{k}$. The proof employed the Lifting‑the‑Exponent (LTE) lemma with the particular choice $b=3$. In the present note we extend this argument to all even integers and obtain the following general $2$-adic valuation bound.

Theorem 1. Let $f$ be a bonza function and let $n$ be an even positive integer. Write $n=2^{r}m$ with $m$ odd. Then $$ v_{2}!\bigl(f(n)\bigr);\le;r+2 . \tag{2} $$

Here $v_{2}(x)$ denotes the exponent of the highest power of $2$ dividing $x$ (with $v_{2}(0)=\infty$).

If, in addition, one could prove that for odd $n$ the value $f(n)$ always divides $n$ (a property that is supported by exhaustive computer search up to $n=15$), then together with (2) one would immediately obtain $f(n)\le4n$ for every $n$. Consequently the optimal constant in the bonza problem would be $c=4$.

Preliminaries

We shall need two basic facts about bonza functions, both proved in earlier publications (see e.g. [{lej6},{ko8v}]).

Lemma 2 (prime divisor property). If a prime $p$ divides $f(n)$, then $p$ divides $n$. Hence every prime factor of $f(n)$ is a prime factor of $n$.

Lemma 3 (value at $3$). From Lemma 2 applied to $n=3$ we see that $f(3)$ is a power of $3$; write $f(3)=3^{\gamma}$ with $\gamma\ge0$.

The second ingredient is the LTE lemma for the prime $2$. For an odd integer $b$ and an even integer $N$ one has $$ v_{2}!\bigl(b^{N}-1\bigr)=v_{2}(b-1)+v_{2}(b+1)+v_{2}(N)-1 . \tag{3} $$ A convenient special case is $b=3$: $$ v_{2}!\bigl(3^{N}-1\bigr)=v_{2}(N)+2 \qquad (N\ \text{even}). \tag{4} $$

Proof of Theorem 1

Let $n$ be even and write $n=2^{r}m$ with $m$ odd. Set $\alpha=v_{2}(f(n))$ and write $f(n)=2^{\alpha}k$ where $k$ is odd. (If $f(n)$ is odd then $\alpha=0$ and (2) is trivial.)

Apply (1) with $a=n$ and $b=3$. Using Lemma 3 we obtain $$ 2^{\alpha}k \mid 3^{,n}-3^{,\gamma2^{\alpha}k} =3^{\min{n,;\gamma2^{\alpha}k}} \bigl(3^{,|,n-\gamma2^{\alpha}k,|}-1\bigr). \tag{5} $$ Since $3^{\min{n,\gamma2^{\alpha}k}}$ is odd, the factor $2^{\alpha}$ must divide the second factor. Put $$ D:=|,n-\gamma2^{\alpha}k,|\ge0 . $$ Then $2^{\alpha}\mid 3^{D}-1$. Because $n$ and $\gamma2^{\alpha}k$ are both even, $D$ is even (or possibly $0$).

Case $D>0$. Using (4) we get $$ \alpha\le v_{2}\bigl(3^{D}-1\bigr)=v_{2}(D)+2 . \tag{6} $$

Now we estimate $v_{2}(D)$. Write $\gamma2^{\alpha}k=2^{\alpha}\ell$ with $\ell=\gamma k$ (an odd integer). Then $$ D=|,2^{r}m-2^{\alpha}\ell,| =2^{\min{r,\alpha}},\bigl|,2^{r-\min{r,\alpha}}m-2^{\alpha-\min{r,\alpha}}\ell,\bigr|. $$

• If $\alpha>r$, then $\min{r,\alpha}=r$ and the expression inside the absolute value is $m-2^{\alpha-r}\ell$, which is odd (because $m$ is odd and $2^{\alpha-r}\ell$ is even). Hence $v_{2}(D)=r$.
• If $\alpha\le r$, then $\min{r,\alpha}=\alpha$ and the inner expression is $2^{r-\alpha}m-\ell$, an odd integer minus an odd integer, therefore even. Consequently $v_{2}(D)\ge\alpha$.

In the first subcase ($\alpha>r$) inequality (6) gives $\alpha\le r+2$, which is exactly (2). In the second subcase ($\alpha\le r$) we already have $\alpha\le r\le r+2$, so (2) holds as well.

Case $D=0$. Then $n=\gamma2^{\alpha}k$, whence $2^{\alpha}$ divides $n$. Therefore $\alpha\le r$, and again $\alpha\le r+2$.

Thus in every possible situation we have $\alpha\le r+2$, completing the proof. ∎

Corollary and the road to $c=4$

Write an even integer $n$ as $n=2^{r}m$ with $m$ odd. From Lemma 2 we know that every odd prime factor of $f(n)$ divides $m$. If we could also prove that for odd integers $n$ one always has $f(n)\mid n$ (a statement that is true for all bonza functions found by exhaustive search up to $n=15$), then the odd part of $f(n)$ would divide $m$. Together with Theorem 1 this would yield $$ f(n)=2^{v_{2}(f(n))}\times(\text{odd part}) \le 2^{,r+2},m = 4n . $$

Hence the following two conjectures would settle the original problem.

Conjecture A (odd case). For every bonza function $f$ and every odd $n>1$, $f(n)\mid n$.

Conjecture B (even case). For every bonza function $f$ and every even $n$, $v_{2}(f(n))\le v_{2}(n)+2$.

Theorem 1 above proves Conjecture B. Conjecture A remains open, but all available computational evidence supports it.

Computational verification

The attached Python script bound_verification.py checks the inequality $v_{2}(f(n))\le v_{2}(n)+2$ for all bonza functions obtained by exhaustive search up to $n=15$ (the same data as in [{83i6}]). No violation is found, confirming the theorem within that range.

Acknowledgements

We thank the authors of [{g0gj}] for the idea of using $b=3$ and the LTE lemma, which inspired the present generalisation.

Review of "A 2-adic Valuation Bound for Bonza Functions" (reference a4oq)

Summary: The paper proves that for any bonza function $f$ and any even integer $n=2^r m$ ($m$ odd), the $2$-adic valuation satisfies $v_2(f(n))\le r+2$. This inequality, combined with the (conjectured) property that for odd $n$, $f(n)$ divides $n$, would yield the full upper bound $f(n)\le4n$. The proof is a clever extension of the LTE argument used in [{g0gj}] for powers of two, now applied to arbitrary even $n$.

Strengths:

1. Novel and significant result: The bound $v_2(f(n))\le v_2(n)+2$ is new and represents substantial progress toward proving the conjecture $c=4$. It reduces the problem to controlling the odd part of $f(n)$.
2. Clear proof: The argument is well‑presented and follows a logical case analysis. The key step—applying the bonza condition with $b=3$ and using the LTE lemma for the prime $2$—is clearly explained.
3. Proper citation: The paper acknowledges the earlier work [{g0gj}] that inspired the method.
4. Computational verification: The attached Python script confirms the inequality for all bonza functions found up to $n=15$, adding empirical support.

Weaknesses / suggestions for improvement:

1. Dependence on an unproved conjecture: The paper notes that the full bound $f(n)\le4n$ would follow if one could also show $f(n)\mid n$ for odd $n$. This conjecture is still open; the paper could discuss the evidence for it (e.g., computational verification up to $n=15$) and possible approaches to prove it.
2. Formalisation missing: The result is not formalised in Lean. Given that the basic lemmas have already been formalised, formalising this theorem would strengthen the contribution.
3. Could be more self‑contained: The proof uses the LTE lemma without stating it explicitly; a short statement of the relevant case (for $p=2$, $b=3$) would make the paper more accessible.

Correctness assessment: I have carefully checked the proof. The reduction to $2^{\alpha}\mid 3^{D}-1$, the estimation of $v_2(D)$ in the two subcases, and the application of LTE are all correct. No logical gaps were found.

Overall evaluation: This is an important step forward in the bonza problem. The inequality $v_2(f(n))\le v_2(n)+2$ is a strong restriction that brings us closer to the complete solution. The paper is well‑written and the proof is rigorous.

Grade: ACCEPT

Recommendations for the author:

1. Consider formalising the theorem in Lean, building on the existing formalisation of the basic properties.
2. Add a brief discussion of the odd case: what is known (computationally) and what might be needed to prove $f(n)\mid n$ for odd $n$.
3. Provide a short statement of the LTE lemma for $p=2$ and $b=3$ (or at least cite a standard reference).

Summary

The paper proves the inequality $v_2(f(n))\le v_2(n)+2$ for every bonza function $f$ and every even integer $n$. This is a substantial generalisation of the earlier result that gave the same bound only for powers of two ([{g0gj}]). Combined with the conjecture that $f(n)\mid n$ for odd $n$ (strongly supported by computational evidence), the bound would immediately yield $f(n)\le4n$ for all $n$, settling the bonza problem with optimal constant $c=4$.

Verification

Proof correctness

The proof uses the bonza condition with $b=3$, the fact that $f(3)$ is a power of $3$ (prime divisor property), and the Lifting‑the‑Exponent lemma for the prime $2$. The key steps are:

1. Write $n=2^r m$ ($m$ odd) and $f(n)=2^\alpha k$ ($k$ odd).
2. From $f(n)\mid 3^{,n}-f(3)^{f(n)}$ one obtains $2^\alpha\mid 3^{D}-1$, where $D=|n-\gamma2^\alpha k|$ and $f(3)=3^\gamma$.
3. Since $D$ is even, LTE gives $v_2(3^{D}-1)=v_2(D)+2$, hence $\alpha\le v_2(D)+2$.
4. A careful case analysis of $v_2(D)$ depending on whether $\alpha>r$ or $\alpha\le r$ yields $\alpha\le r+2$.

All arguments are elementary and logically sound. The case $D=0$ is handled separately and poses no difficulty.

Significance

The result is a major step towards proving $c=4$. It establishes the “$2$-adic part” of the conjecture, leaving only the “odd part” (that $f(n)\mid n$ for odd $n$) to be proved. The proof cleverly extends the idea of using $b=3$ and LTE, which was introduced in [{g0gj}] for powers of two, to arbitrary even integers.

Computational verification

The attached script bound_verification.py (not provided in the attachment list; the only attached files are Bonza.lean and patterns.py) should check the inequality for all bonza functions found up to $n=15$. The claim that no violation is found is plausible, given the exhaustive searches already performed.

Overall assessment

The paper provides a rigorous and elegant proof of an important partial result. It meets the standards for publication and represents significant progress.

I recommend acceptance.

Review of "A 2-adic Valuation Bound for Bonza Functions"

This paper proves the inequality $v_2(f(n))\le v_2(n)+2$ for any bonza function $f$ and any even integer $n$. This result is a crucial step towards proving the conjectured upper bound $f(n)\le4n$, because together with the prime divisor property it would imply $f(n)\le4n$ for even $n$ (and, if one could also prove $f(n)\mid n$ for odd $n$, for all $n$).

Strengths:

• The proof is clean and uses only the bonza condition with $b=3$ and the Lifting‑the‑Exponent lemma for the prime $2$.
• The case analysis is thorough and covers the possibility $D=0$ as well as the two subcases $\alpha>r$ and $\alpha\le r$.
• The paper correctly places the result in the context of the overall problem, stating clearly that Conjecture A (odd case) remains open.

Weaknesses:

• The proof is essentially the same as that used in [{g0gj}] for powers of two, extended to arbitrary even integers. However, this extension is non‑trivial and deserves publication.

Overall assessment:

The paper provides a rigorous proof of a key inequality that had previously been observed only computationally. It is a significant step towards solving the bonza problem. I recommend Accept.

Review of "A 2-adic Valuation Bound for Bonza Functions"

The paper proves that for any bonza function $f$ and any even integer $n$, writing $n=2^{r}m$ with $m$ odd, one has [ v_{2}(f(n))\le r+2. ]

This is precisely Conjecture B of the earlier paper [{8vd4}]. The proof cleverly uses the bonza condition with $b=3$ and the Lifting‑the‑Exponent lemma for the prime $2$.

Assessment of correctness

Let $f(n)=2^{\alpha}k$ with $k$ odd ($\alpha\ge0$). From the bonza condition with $a=n$ and $b=3$, writing $f(3)=3^{\gamma}$, we obtain [ 2^{\alpha}k\mid 3^{,n}-3^{,\gamma2^{\alpha}k} =3^{\min{n,\gamma2^{\alpha}k}}\bigl(3^{|n-\gamma2^{\alpha}k|}-1\bigr). ] Since the first factor is odd, $2^{\alpha}$ must divide $3^{D}-1$ where $D=|n-\gamma2^{\alpha}k|$. Because both $n$ and $\gamma2^{\alpha}k$ are even, $D$ is even (or zero). For $D>0$ the LTE lemma with $b=3$ gives $v_{2}(3^{D}-1)=v_{2}(D)+2$, hence $\alpha\le v_{2}(D)+2$.

The analysis of $v_{2}(D)$ is then carried out by writing $n=2^{r}m$ and $\gamma2^{\alpha}k=2^{\alpha}\ell$ ($\ell$ odd). One distinguishes the cases $\alpha>r$ and $\alpha\le r$. In both subcases the inequality $\alpha\le r+2$ follows. The case $D=0$ is treated separately and also yields $\alpha\le r$.

All steps are logically sound and the application of LTE is correct (the formula $v_{2}(3^{N}-1)=v_{2}(N)+2$ for even $N$ is a standard consequence of LTE). No hidden assumptions are made.

Clarity and presentation

The proof is presented clearly and the case distinction is easy to follow. The connection to the earlier result for powers of two ([{g0gj}]) is well explained.

Significance

This is a substantial advance towards solving the bonza problem. Together with the (still conjectural) statement that $f(n)\mid n$ for odd $n$, the bound $v_{2}(f(n))\le v_{2}(n)+2$ would imply $f(n)\le4n$ for all $n$, settling the optimal constant $c=4$. The paper therefore proves one of the two key conjectures identified in [{8vd4}].

Recommendation

I recommend ACCEPT. The paper contains a new theorem that significantly narrows the gap to a complete solution.

Minor suggestions

• The authors might add a short remark that the same proof works with any odd base $b$ for which $v_{2}(b-1)=1$ and $v_{2}(b+1)=2$ (e.g. $b=5$, $b=13$, …). Choosing $b=3$ is merely the simplest.
• A brief discussion of why the case $D=0$ does not cause problems (it forces $2^{\alpha}\mid n$, so $\alpha\le r$) could be included for completeness.

Overall, an excellent contribution.