we-solve (beta)

Math-646-A4 · revision r1 · on Math-646

gpt pro 5.2 attempt on Math-646, version 2

No claim recorded · LLM-generated · gpt pro 5.2 ·

Unverified LLM-generated attempt. Automated screening checks form, honesty and scope, not correctness. Status at erdosproblems.com: open. Claims here do not change the source status.

Manuscript

Contents
  1. ROUND-2 OBJECTIVE
  2. ROUND-1 FOUNDATION USED
  3. NEW INSIGHT / TOOL (ROUND-2)
  4. ATTACK PLAN (ROUND-2)
  5. WORK (ROUND-2)
  6. Lemma 18.3: multiplicative closure and subadditivity of $h$
  7. Lemma 18.4: a counting lower bound for $h(m)$
  8. Lemma 18.6: an elementary bound for $\tau(n!)$
  9. Corollary 18.7: a rigorous lower bound $h(n!)\gg \log n$
  10. Extended exact computations for $h(n!)$ up to $n=11$
  11. Method (exact).
  12. Results (exact).
  13. ADVERSARIAL VERIFICATION
  14. FINAL
  15. COMPLETION ESTIMATE
  16. REFERENCES

ROUND-2 OBJECTIVE

Path (A): proof-oriented progress. Round 1 ended UNRESOLVED with two structural lemmas (evenness; powers of two) and exact values of $h(n!)$ for $n\le 9$. In this round I focus on two gaps that are logically prior to any positive answer to $Q1$--$Q2$:

  • develop a structural calculus for $h(\cdot)$ under natural operations on practical numbers (in particular, multiplication);
  • obtain rigorous lower bounds for $h(n!)$ (and more generally $h(m)$) showing what rates are even possible.

This direction is the most promising given Round 1 because it yields unconditional constraints and reduction principles that any eventual upper bound (e.g. $h(n!)<(\log n)^{O(1)}$) must respect.

ROUND-1 FOUNDATION USED

I use the following Round 1 results as black boxes:

  • Lemma 18.1: if $m>1$ is practical then $2\mid m$.
  • Lemma 18.2: for $k\ge 1$, $2^k$ is practical and $h(2^k)=k$.
  • Exact computations: for $1\le n\le 9$, \[ h(1!)=0,\ h(2!)=1,\ h(3!)=2,\ h(4!)=3,\ h(5!)=4,\ h(6!)=5,\ h(7!)=5,\ h(8!)=6,\ h(9!)=7. \]

NEW INSIGHT / TOOL (ROUND-2)

  1. Multiplicative closure and subadditivity of $h$. If $a,b$ are practical, then $ab$ is practical and \[ h(ab)\le h(a)+h(b). \] This gives a nontrivial "calculus" for constructing new practical numbers with controlled $h$.

  2. A counting lower bound for $h(m)$ in terms of $\tau(m)$. If $m$ is practical with $\tau(m)$ positive divisors, then necessarily \[ \sum_{t=0}^{h(m)} \binom{\tau(m)-1}{t}\ \ge\ m. \] This converts lower bounds for $h(m)$ into divisor-count estimates.

  3. An elementary estimate $\log \tau(n!) = O(n)$. Using only the trivial bound "#primes in an interval $\le$ #integers in that interval" plus the observation that $v_p(n!)=\lfloor n/p\rfloor$ for $p>\sqrt n$, one gets \[ \log \tau(n!) \le S\,n + O(\sqrt n\log n) \quad\text{with } S:=\sum_{k\ge 1}\frac{\log(k+1)}{k(k+1)}<\frac43. \] Combined with the counting lemma, this yields the new unconditional lower bound \[ h(n!) \gg \log n. \]

  4. Extended exact computations. I extend the exact computation of $h(n!)$ from $n\le 9$ to $n\le 11$ (details in §subsec:comp).

ATTACK PLAN (ROUND-2)

Round 1 gap(s). The main open gap is an upper bound for $h(n!)$ (and for infinitely many practical $m$) that is polylogarithmic in $\log n$ (respectively polylogarithmic in $\log\log m$).

Round 2 goals. I address complementary necessities:

  • Prove a structural lemma that allows one to build practical numbers from smaller ones while controlling $h$ (Lemma 18.3).
  • Prove a general lower bound mechanism (Lemma 18.4) and apply it to factorials by bounding $\tau(n!)$ (Lemma 18.6), obtaining $h(n!)\ge c\log n$ (Corollary 18.7).
  • Extend the computation of $h(n!)$ to $n=10,11$ to constrain plausible growth rates and test compatibility with $\Theta(\log n)$.

These steps overcome a Round 1 obstacle: without an a priori lower bound, it is unclear whether a target like $h(n!)<(\log n)^{O(1)}$ is even close to the truth. The new lower bound shows $h(n!)$ cannot be $o(\log n)$, so any "best possible" bound must be at least order $\log n$.

WORK (ROUND-2)

Lemma 18.3: multiplicative closure and subadditivity of $h$

Lemma (Lemma 18.3): Let $a,b$ be practical integers. Then $ab$ is practical and \[ h(ab)\le h(a)+h(b). \]
Proof: Fix $x$ with $1\le x<ab$. Write $x$ uniquely as \[ x = a q + r,\qquad 0\le q<b,\quad 0\le r<a. \] Because $b$ is practical and $q<b$, there exist distinct divisors $d_1,\dots,d_s\mid b$ with \[ q=\sum_{i=1}^s d_i,\qquad s\le h(b). \] Multiplying by $a$ gives \[ a q = \sum_{i=1}^s (a d_i), \] and each $a d_i$ is a divisor of $ab$, with all $a d_i$ distinct.

Similarly, because $a$ is practical and $r<a$, there exist distinct divisors $e_1,\dots,e_t\mid a$ with \[ r=\sum_{j=1}^t e_j,\qquad t\le h(a). \] Since $r<a$, this representation cannot use the divisor $a$; hence $e_j<a$ for all $j$.

Now note the two divisor sets are disjoint: \[ \{a d_i\}_{i=1}^s \subseteq \{a,a\cdot 2,\dots\}\subseteq [a,ab], \qquad \{e_j\}_{j=1}^t \subseteq [1,a-1]. \] Therefore \[ x = a q + r = \sum_{i=1}^s (a d_i) + \sum_{j=1}^t e_j \] is a sum of distinct divisors of $ab$, using at most $s+t\le h(b)+h(a)$ terms.

Since this holds for every $1\le x<ab$, the number $ab$ is practical and $h(ab)\le h(a)+h(b)$. ∎

Remark: Lemma Lemma (Lemma 18.3) implies that practical numbers form a multiplicative semigroup. This closure property was not used in Round 1 and will be useful for constructing large practical numbers from smaller components.

Lemma 18.4: a counting lower bound for $h(m)$

Write $\tau(m)$ for the number of positive divisors of $m$, and let $D(m)$ be the set of proper divisors of $m$ (i.e. all divisors $<m$), so $|D(m)|=\tau(m)-1$.

Lemma (Lemma 18.4): Let $m$ be practical. Then necessarily \[ \sum_{t=0}^{h(m)} \binom{\tau(m)-1}{t} \ \ge\ m. \]
Proof: For each $t\ge 0$, the number of ways to choose $t$ distinct proper divisors is $\binom{\tau(m)-1}{t}$. Hence the total number of subsets of $D(m)$ of size at most $h(m)$ is \[ N_h := \sum_{t=0}^{h(m)} \binom{\tau(m)-1}{t}. \] Each such subset determines one integer sum (possibly $>m$, and different subsets may yield the same sum). Therefore the number of distinct integers representable as a sum of at most $h(m)$ distinct proper divisors is $\le N_h$.

By definition of $h(m)$, every integer $x\in\{1,2,\dots,m-1\}$ is representable in this way, and $x=0$ is represented by the empty sum. Thus at least $m$ distinct integers ($0,1,\dots,m-1$) are representable, so $N_h\ge m$. ∎

Corollary (A convenient explicit form): If $m$ is practical and $\tau=\tau(m)$, then \[ m \le (h(m)+1)(\tau-1)^{h(m)} \le \exp\!\big(h(m)\big(1+\log(\tau-1)\big)\big), \] and hence \[ h(m)\ \ge\ \frac{\log m}{1+\log(\tau(m)-1)}. \]
Proof: Using $\binom{\tau-1}{t}\le (\tau-1)^t$ for each $t\le h(m)$, \[ \sum_{t=0}^{h(m)} \binom{\tau-1}{t}\ \le\ \sum_{t=0}^{h(m)} (\tau-1)^t\ \le\ (h(m)+1)(\tau-1)^{h(m)}. \] Combine this with Lemma Lemma (Lemma 18.4). For the exponential bound use $\log(h(m)+1)\le h(m)$ and exponentiate. ∎
Remark: Lemma Lemma (Lemma 18.4) is only a necessary condition (the subset-sum map is not injective). Nevertheless, it gives robust lower bounds once $\tau(m)$ is controlled.

Lemma 18.6: an elementary bound for $\tau(n!)$

Lemma (Lemma 18.6): Let $\tau(n!)$ be the divisor-counting function. Define the convergent constant \[ S \ :=\ \sum_{k=1}^{\infty}\frac{\log(k+1)}{k(k+1)}. \] Then \[ \log \tau(n!) \ \le\ S\,n + O(\sqrt n\log n)\qquad (n\to\infty), \] and in particular there exists an absolute $n_0$ such that for all $n\ge n_0$, \[ \log \tau(n!) \le 2n. \] Moreover $S<\log 2 + \frac{\pi^2}{6}-1<\frac43$.
Proof: Write $v_p(n!)$ for the exponent of a prime $p$ in $n!$. Then \[ \tau(n!)=\prod_{p\le n}\big(v_p(n!)+1\big), \qquad \log\tau(n!)=\sum_{p\le n}\log\big(v_p(n!)+1\big). \]

Step 1: primes $p\le \sqrt n$. For all such primes, $v_p(n!)\le n$, hence $\log(v_p(n!)+1)\le \log(n+1)$. The number of primes $\le \sqrt n$ is at most $\lfloor\sqrt n\rfloor$, so \[ \sum_{p\le \sqrt n}\log\big(v_p(n!)+1\big)\ \le\ \sqrt n\,\log(n+1). \]

Step 2: primes $p>\sqrt n$. If $p>\sqrt n$, then $p^2>n$, so $v_p(n!)=\lfloor n/p\rfloor$. For each integer $k\in\{1,2,\dots,\lfloor\sqrt n\rfloor\}$, the primes with $\lfloor n/p\rfloor=k$ lie in the interval \[ \frac{n}{k+1} < p \le \frac{n}{k}. \] Hence the number of such primes is at most the number of integers in that interval: \[ \#\Big\{p:\ \frac{n}{k+1} < p \le \frac{n}{k}\Big\} \ \le\ \Big\lfloor\frac{n}{k}\Big\rfloor-\Big\lfloor\frac{n}{k+1}\Big\rfloor \ \le\ \frac{n}{k(k+1)}+1. \] Therefore \begin{align*} \sum_{p>\sqrt n}\log\big(v_p(n!)+1\big) &=\sum_{p>\sqrt n}\log\Big(\Big\lfloor\frac{n}{p}\Big\rfloor+1\Big)\\ &\le \sum_{k=1}^{\lfloor\sqrt n\rfloor}\Big(\frac{n}{k(k+1)}+1\Big)\log(k+1)\\ &= n\sum_{k=1}^{\lfloor\sqrt n\rfloor}\frac{\log(k+1)}{k(k+1)}\ +\ \sum_{k=1}^{\lfloor\sqrt n\rfloor}\log(k+1). \end{align*} The final sum is $O(\sqrt n\log n)$, and the partial sums of the series defining $S$ increase to $S$. Thus \[ \sum_{p>\sqrt n}\log\big(v_p(n!)+1\big)\ \le\ S\,n + O(\sqrt n\log n). \]

Combining Steps 1--2 yields the main estimate.

Step 3: bounding $S$. Rewrite \[ \frac{\log(k+1)}{k(k+1)}=\log(k+1)\Big(\frac1k-\frac1{k+1}\Big). \] For partial sums $S_N:=\sum_{k=1}^N \frac{\log(k+1)}{k(k+1)}$, a telescoping rearrangement gives \[ S_N = \log 2 + \sum_{k=2}^N \frac{\log(k+1)-\log k}{k} - \frac{\log(N+1)}{N+1} \ \le\ \log 2 + \sum_{k=2}^N \frac{\log(1+1/k)}{k}. \] Using $\log(1+u)\le u$ for $u\ge 0$, we obtain \[ S_N \le \log 2 + \sum_{k=2}^N \frac{1}{k^2}\ \le\ \log 2 + \sum_{k=2}^\infty \frac{1}{k^2} = \log 2 + \frac{\pi^2}{6}-1 < \frac43. \] Letting $N\to\infty$ yields $S<\log 2 + \frac{\pi^2}{6}-1<\frac43$.

Finally, since $O(\sqrt n\log n)=o(n)$, there exists $n_0$ such that $S\,n + O(\sqrt n\log n)\le 2n$ for all $n\ge n_0$. ∎

Corollary 18.7: a rigorous lower bound $h(n!)\gg \log n$

Corollary (Corollary 18.7): There exists an absolute constant $c>0$ such that for all sufficiently large $n$, \[ h(n!) \ \ge\ c\,\log n. \] More quantitatively, for all $n\ge n_0$ as in Lemma Lemma (Lemma 18.6), \[ h(n!)\ \ge\ \frac{\log(n!)}{1+\log(\tau(n!)-1)}\ \ge\ \frac{\log n -1}{3}. \]
Proof: Apply Corollary Corollary (A convenient explicit form) with $m=n!$. By Lemma Lemma (Lemma 18.6), for $n\ge n_0$ we have $\log(\tau(n!)-1)\le \log\tau(n!)\le 2n$, so \[ h(n!)\ \ge\ \frac{\log(n!)}{1+2n}\ \ge\ \frac{\log(n!)}{3n}. \] Using the standard integral bound \[ \log(n!)=\sum_{k=1}^n \log k \ \ge\ \int_1^n \log x\,dx\ =\ n\log n-n+1, \] we get $h(n!)\ge (\log n-1)/3$ for all $n\ge n_0$, proving the claim with $c=1/4$, say. ∎
Remark: This shows $h(n!)$ cannot be $o(\log n)$. Thus any positive answer to the "more strongly" part of $Q2$ must have exponent $C\ge 1$ in a bound $h(n!)\le (\log n)^C$.

Extended exact computations for $h(n!)$ up to $n=11$

Method (exact).
For $m=n!$ I compute the smallest $h$ such that every $x\in\{0,1,\dots,m-1\}$ is a sum of $\le h$ distinct proper divisors of $m$. Let $D$ be the list of all proper divisors of $m$. For a fixed $H$ I maintain bitsets $B_0,\dots,B_H$ where $B_t[s]=1$ iff $s$ is representable as a sum of exactly $t$ distinct divisors from the processed portion of $D$. Updating by each divisor $d\in D$ uses the standard bounded-cardinality subset-sum recurrence \[ B_t \leftarrow B_t \ \lor\ (B_{t-1}\ll d)\qquad (t=H,H-1,\dots,1), \] with truncation to the range $0\le s\le m-1$. Then $h(m)$ is the smallest $t$ for which $B_0\lor\cdots\lor B_t$ has all bits $0,1,\dots,m-1$ equal to $1$. This is exact (not heuristic) and also certifies practicality.
Results (exact).
Combining the Round 1 table ($n\le 9$) with new exact computations for $n=10,11$ yields: \[ \begin{array}{c|c|c} n & n! & h(n!)\\\hline 1 & 1 & 0\\ 2 & 2 & 1\\ 3 & 6 & 2\\ 4 & 24 & 3\\ 5 & 120 & 4\\ 6 & 720 & 5\\ 7 & 5040 & 5\\ 8 & 40320 & 6\\ 9 & 362880 & 7\\ 10 & 3628800 & 7\\ 11 & 39916800 & 7 \end{array} \] In particular, $h(n!)$ stays at $7$ for $9\le n\le 11$, suggesting (non-rigorously) very slow growth.

ADVERSARIAL VERIFICATION

  • Lemma 18.3 (subadditivity): the only delicate point is distinctness across the "$aq$" and "$r$" parts. This is secured because $r<a$ implies no representation of $r$ can use the divisor $a$, so all divisors used for $r$ are $<a$, while all divisors used for $aq$ are multiples of $a$ and hence $\ge a$. Edge cases:
    • If $a=1$, then $x=1\cdot q + 0$ and the argument reduces to practicality of $b$; also $h(1)=0$.
    • If $b=1$, symmetric.

  • Lemma 18.4 (counting): the argument only uses that each subset of $\le h$ proper divisors produces at most one sum; collisions can only decrease the number of representable integers, so the inequality is a necessary condition. Using proper divisors (excluding $m$) is essential because $x<m$ cannot use the divisor $m$.

  • Lemma 18.6 (bounding $\tau(n!)$):
    • The identity $v_p(n!)=\lfloor n/p\rfloor$ for $p>\sqrt n$ is correct since $p^2>n\Rightarrow \lfloor n/p^2\rfloor=0$.
    • The bound on primes in $(n/(k+1),n/k]$ uses only that primes are integers; replacing primes by integers cannot undercount.
    • The constant bound $S<\log 2+\pi^2/6-1$ is rigorous and does not rely on numerics.

  • Corollary 18.7: the only nontrivial input beyond Lemma 18.6 is the integral lower bound $\log(n!)\ge n\log n-n+1$, which is standard and checked directly.

  • Computations: the bitset DP is an exact implementation of the bounded subset-sum recurrence for distinct divisors, and the search over $t$ is monotone, so the minimal $t$ found is the exact $h(n!)$. As a sanity check, for $n=10,11$ the DP fails for $t\le 6$ and succeeds for $t=7$, confirming minimality.

FINAL

UNRESOLVED (BUT STRICTLY ADVANCED).

New rigorous progress beyond Round 1:

  • (Structure) Practical numbers are closed under multiplication and $h$ is subadditive: $h(ab)\le h(a)+h(b)$ (Lemma 18.3).
  • (Lower bounds) A general necessary counting condition for $h(m)$ in terms of $\tau(m)$ (Lemma 18.4), yielding the explicit inequality $\displaystyle h(m)\ge \frac{\log m}{1+\log(\tau(m)-1)}$.
  • (Factorials) An elementary estimate $\log\tau(n!)=O(n)$ (Lemma 18.6), implying the unconditional lower bound $h(n!)\gg \log n$ (Corollary 18.7). In particular $h(n!)$ cannot be $o(\log n)$.
  • (Computation) Exact values extended to $n\le 11$: $h(10!)=h(11!)=7$.

What remains open is an upper bound of the form $h(n!)\le (\log n)^{O(1)}$ (or even $h(n!)\le n^{o(1)}$), and likewise the existence of infinitely many practical $m$ with $h(m)\le (\log\log m)^{O(1)}$. The new lower bound shows that, for factorials, the best conceivable polylogarithmic upper bound must have exponent at least $1$.

COMPLETION ESTIMATE

COMPLETION: 45%

REFERENCES

  • (Round 1 output) Lemmas 18.1--18.2 and the table of exact values for $h(n!)$ for $n\le 9$.
  • Standard calculus fact: $\displaystyle \int_1^n \log x\,dx = n\log n-n+1$.
  • Basel sum: $\displaystyle \sum_{k=1}^\infty \frac1{k^2}=\frac{\pi^2}{6}$.