21
$\begingroup$

Do for every natural number $n$ exist (possibly negative) integers $a_p$, finitely many of them nonzero, such that $$\log(n) = \sum_{p \text{ prime}} a_p \log(p-1)\,?$$ Equivalently: $$n = \prod_{p \text{ prime}} (p-1)^{a_p}.$$

Comment: This would follow from the hypothesis underlying this answer by GH from MO to Given a prime $p$ and by Dirichlet a prime $q = k\cdot p+1$ — minimal of this form — does the number $k = (q-1)/p$ have only prime divisors $<p$? by induction on $n$.

This representation would be unique, if we allow only linearly independent primes in the summation: Linear independent prime numbers?

Examples:

############################################################
# SageMath script:
# Recursive representation of log(n) as
#
#    log(n) = sum_{q} a_q * log(q-1)
#
# where the primes q arise recursively as the smallest
# primes of the form q = k*p + 1 (Dirichlet-style),
# and are linearly independent in the sense of your construction.
#
# Author :  me & ChatGPT (recursive version)
############################################################

from sage.all import (
    ZZ, factor, is_prime
)

############################################################
# Global storage:
#   rep[n]   : dict {q : a_q} representing
#              log n = sum_q a_q * log(q-1)
#   LI_primes: set of "basis primes" q that appear as q = k*p+1
############################################################

rep = {}           # n -> {q : a_q}
LI_primes = set()  # primes q introduced as "basis" symbols


def _add_coeffs_inplace(target, source, factor=1):
    """
    In-place: target[q] += factor * source[q].
    Remove entries that become zero.
    """
    for q, a in source.items():
        new_val = target.get(q, 0) + factor * a
        if new_val == 0:
            if q in target:
                del target[q]
        else:
            target[q] = new_val
    return target


############################################################
# Recursive representation of log(n)
############################################################

def repr_log(n):
    """
    Return a dictionary {q : a_q} such that

        log(n) = sum_q a_q * log(q-1),

    where the summation is over primes q produced
    recursively by the procedure below.

    The representation is unique (given this recursive
    construction) once it exists.
    """
    n = ZZ(n)
    if n <= 0:
        raise ValueError("n must be a positive integer.")

    # already computed?
    if n in rep:
        return rep[n]

    # base case: n = 1
    if n == 1:
        rep[n] = {}
        return rep[n]

    # if n is prime: use the special recursion with q = k*p+1
    if is_prime(n):
        return _repr_log_prime(n)

    # otherwise: factor n and use log(n) = sum e_i * log(p_i)
    coeffs = {}
    for p, e in factor(n):
        p = ZZ(p)
        cp = repr_log(p)  # representation for the prime p
        for _ in range(e):
            _add_coeffs_inplace(coeffs, cp, factor=1)

    rep[n] = coeffs
    return coeffs


def _repr_log_prime(p):
    """
    Internal: representation of log(p) for p prime using the rule:

        choose minimal k >= 1 such that q = k*p + 1 is prime,
        then log(p) = log(q-1) - log(k),

    and log(k) is expressed recursively (k < p).
    """
    p = ZZ(p)
    if p in rep:
        return rep[p]

    # Find minimal k such that q = k*p + 1 is prime
    found = False
    for k in range(1, int(p) + 1):
        q = k * p + 1
        if is_prime(q):
            found = True
            k = ZZ(k)
            q = ZZ(q)
            break

    if not found:
        raise ValueError(f"No prime of the form q = k*p + 1 found for p = {p} with k <= p.")

    # q is a new (or reused) "basis prime"
    LI_primes.add(q)

    # log(p) = log(q-1) - log(k)
    # => coefficients: {q: 1} - repr_log(k)
    coeffs = {q: 1}

    if k > 1:
        coeffs_k = repr_log(k)   # representation of log(k)
        _add_coeffs_inplace(coeffs, coeffs_k, factor=-1)

    rep[p] = coeffs
    return coeffs


############################################################
# Pretty-printing
############################################################

def print_log_identity(n):
    """
    Pretty-print the identity:

        log(n) = sum_{q} a_q * log(q-1),

    with primes q produced by the recursive construction.
    """
    coeffs = repr_log(n)

    # Build RHS as a string
    terms = []
    for q in sorted(coeffs.keys()):
        a_q = coeffs[q]
        if a_q == 1:
            terms.append(f"log({q}-1)")
        elif a_q == -1:
            terms.append(f"-log({q}-1)")
        else:
            terms.append(f"{a_q}*log({q}-1)")

    if not terms:
        rhs = "0"
    else:
        rhs = terms[0]
        for t in terms[1:]:
            # if it starts with "-", write " - ..." otherwise " + ..."
            if t.startswith("-"):
                rhs += " " + t
            else:
                rhs += " + " + t

    print(f"log({n}) = {rhs}")


def show_LI_primes():
    """
    Print the list of recursively generated 'LI primes' q
    (i.e. those that appear as q = k*p+1).
    """
    print("Recursively generated LI primes q (basis primes):")
    print(sorted(LI_primes))


############################################################
# Example usage in Sage:
#
#   for p in primes(2, 50):
#       print_log_identity(p)
#
#   print_log_identity(60)
#   show_LI_primes()
############################################################
for n in range(1,34):
    print_log_identity(n)


log(1) = log(2-1)
log(2) = log(3-1)
log(3) = -log(3-1) + log(7-1)
log(4) = 2*log(3-1)
log(5) = -log(3-1) + log(11-1)
log(6) = log(7-1)
log(7) = -2*log(3-1) + log(29-1)
log(8) = 3*log(3-1)
log(9) = -2*log(3-1) + 2*log(7-1)
log(10) = log(11-1)
log(11) = -log(3-1) + log(23-1)
log(12) = log(3-1) + log(7-1)
log(13) = -2*log(3-1) + log(53-1)
log(14) = -log(3-1) + log(29-1)
log(15) = -2*log(3-1) + log(7-1) + log(11-1)
log(16) = 4*log(3-1)
log(17) = -log(7-1) + log(103-1)
log(18) = -log(3-1) + 2*log(7-1)
log(19) = -log(11-1) + log(191-1)
log(20) = log(3-1) + log(11-1)
log(21) = -3*log(3-1) + log(7-1) + log(29-1)
log(22) = log(23-1)
log(23) = -log(3-1) + log(47-1)
log(24) = 2*log(3-1) + log(7-1)
log(25) = -2*log(3-1) + 2*log(11-1)
log(26) = -log(3-1) + log(53-1)
log(27) = -3*log(3-1) + 3*log(7-1)
log(28) = log(29-1)
log(29) = -log(3-1) + log(59-1)
log(30) = -log(3-1) + log(7-1) + log(11-1)
log(31) = -log(11-1) + log(311-1)
log(32) = 5*log(3-1)
log(33) = -2*log(3-1) + log(7-1) + log(23-1)
Improve this question
$\endgroup$
5
  • 24
    $\begingroup$ It would be more natural to write $n = \prod_{p \text{ prime}} (p-1)^{a_p}$. $\endgroup$ Commented Nov 16 at 22:18
  • 1
    $\begingroup$ It suffices to obtain all primes. Suppose we consider only primes where $p-1$ is $x$-smooth. We get a $\pi(x)$-dimensional lattice. Looking at its dual, we can see that the lattice isn't $\mathbb{Z}^{\pi(x)}$ iff there's a vector $a$ of rational numbers, not all of them integer, such that $\sum_{p_i\le x}{a_iv_{p_i}(p-1)}\in\mathbb{Z}$ whenever $p-1$ is $x$-smooth. Multiplying by a common denominator $m$ we get that $m\mid\sum_{p_i\le x}{b_iv_{p_i}(p-1)}$ for some non-zero vector $b$ mod $m$. I think this might be possible to rule out using sieve methods, but I don't know enough to do that. $\endgroup$ Commented Nov 17 at 6:10
  • $\begingroup$ Isn't the Q. trivial? -- if $\ n>2\ $ is prime then $\ n\ $ is not any product as assumed by the Q. $\endgroup$ Commented Nov 19 at 3:01
  • 1
    $\begingroup$ @WlodAA: The $a_p$ can be negative. $\endgroup$ Commented Nov 19 at 3:03
  • 1
    $\begingroup$ ** Thank you. ** $\endgroup$ Commented Nov 20 at 4:50

2 Answers 2

Reset to default
21
$\begingroup$

For any positive integers $a$ and $b$, by Schinzel's Hypothesis there is a positive integer $k$ such that both $p=ak+1$ and $q=bk+1$ are primes, hence $\frac ab=\frac{p-1}{q-1}$. In 2015, I even conjectured that each positive rational number can be written as $\frac{p_k-1}{p_m-1}$ with $k$ and $m$ both prime, see https://oeis.org/A258803.

Improve this answer
$\endgroup$
0
14
$\begingroup$

By modifying idea from Zhi-Wei Sun's answer, we can unconditionally prove a slightly weaker statement, namely one we get by allowing rational powers (and moreover we can bound the exponent independently of $n$). Indeed, results of Maynard-Tao on bounded intervals with many primes generalize to arbitrary linear forms, as stated e.g. here. We can in particular apply it to linear forms $L_i(x)=n^ix+1$, and the result shows that there is some constant $k$, independent of $n$, such that there are infinitely many $m$ such that at least two of $L_i(m),i=1,\dots,k$ are prime. If say $p=L_i(m),q=L_j(m)$ are prime with $i\neq j$, then $$\frac{p-1}{q-1}=\frac{L_i(m)-1}{L_j(m)-1}=\frac{n^im}{n^jm}=n^{i-j},$$ and hence $n=(p-1)^{1/(i-j)}(q-1)^{-1/(i-j)}$. Moreover, $|i-j|<k$ is uniformly bounded.

In fact, similar argument gives something much stronger - if you consider the subgroup $S$ of the multiplicative group $\Bbb Q^+$ generated by $p-1$ for primes $p$, then this subgroup has finite index: for any $k$ naturals $n_i$, consider $L_i(x)=n_ix+1$. When two of these take a simultaneous prime value, we get that $\frac{n_i}{n_j}=\frac{p-1}{q-1}\in S$, so $n_i,n_j$ land in the same coset. The same is true for any tuple of rationals once we clear denominators, thus we get the index of $S$ in $\Bbb Q^+$ is smaller than $k$.

Improve this answer
$\endgroup$
5
  • 3
    $\begingroup$ Just to spell it out more concretely, the fact that $[\mathbb Q^+:S]<\infty$ means that there is $m>0$ and a finite partition of primes into sets $P_i$, $i<n$, such that $x\in S$ whenever $m\mid\sum_{p\in P_i}v_p(x)$ for all $i<n$. $\endgroup$ Commented Nov 18 at 16:00
  • 2
    $\begingroup$ Getting the index down to one requires ruling out that there is a nonconstant multiplicative function $\lambda$ with $\lambda(p-1)=1$ for all primes $p$. This is of course true but seems hard to prove. $\endgroup$ Commented Nov 18 at 18:59
  • 4
    $\begingroup$ @WillSawin Such a simple-to-state hard problem! I remark that for completely multiplicative functions, it would follow from the standard (hard) conjecture that the least prime congruent to 1 (mod $q$) is always less than $q^2$ (let $q$ be minimal with $\lambda(q)\ne1$...). $\endgroup$ Commented Nov 18 at 23:22
  • $\begingroup$ @GregMartin I actually meant a completely multiplicative function so your implication is unqualified. $\endgroup$ Commented Nov 19 at 1:53
  • 1
    $\begingroup$ @GregMartin It also follows from Schinzel's hypothesis (or just Dickson's conjecture) as noted in Zhi-Wei Sun's answer. $\endgroup$ Commented Nov 19 at 6:11

You must log in to answer this question.

Start asking to get answers

Find the answer to your question by asking.

Ask question

Explore related questions

See similar questions with these tags.