Research · Hardness of the discrete logarithm

The height obstruction to lifting

partial2 sessionsupdated 2026-07-14Paper (PDF · 0.4 MB)

PROVED The literal pcp^c height lower bound is false, while the dependence/rank-conditioned xedni question remains open.

Formal target

Let E/FpE/\mathbb F_p, let E~/Q\widetilde E/\mathbb Q have good reduction EE at pp, and let P~E~(Q)\widetilde P\in\widetilde E(\mathbb Q) reduce to PE(Fp)P\in E(\mathbb F_p).

The proposed target is a lower bound h^(P~)=Ω(pc)\widehat h(\widetilde P)=\Omega(p^c) for an explicit c>0c>0, uniformly over the lifts satisfying the constraints needed by a xedni-calculus attack.

Operational target for this repository

  • Decide whether the literal uniform statement is tenable.
  • Measure one- and multi-point lifts at toy primes, with the height convention and lift-sampling rule stated explicitly.
  • Separate data by the number of prescribed reductions and by Mordell-Weil rank when a rank routine is available.
  • Fit a growth law with stored residuals and state a falsifiable conjecture.
  • State precisely what additional hypotheses and height-theoretic input a proof of an attack-relevant theorem would require.

Falsifiers

  • A proof of the constrained lower bound with an explicit exponent resolves the stated target positively.
  • A construction satisfying the actual attack constraints with heights polynomial in logp\log p refutes the proposed obstruction in that model.
  • A low-height construction outside the attack constraints refutes only the literal uniform statement and identifies a missing hypothesis.

Current disposition

PROVED The literal uniform statement is false: NOTES.md constructs O(logp)O(\log p) single-point lifts and, under an explicit row-rank condition, Ok(logp)O_k(\log p) simultaneous lifts for k4k\leq4.

PROVED The construction does not impose rational dependence or total rank below kk, so the attack-relevant refinement is not resolved.

CITED The primary 2000 failure analysis uses a conditional bound on relation coefficients together with finite-group counting rather than the lower bound stated in the prompt.

State in five lines

PROVED The literal Ω(pc)\Omega(p^c) height target is false. PROVED Single points and full-row-rank tuples with k4k\leq4 admit Ok(logp)O_k(\log p) lifts. EMPIRICAL: 144 variants, relation bound 8 SG-08 found 99 finite relations but only two rational two-torsion relations. PROVED Bounded non-detection is not a Mordell-Weil independence certificate. PROVED SG-09 failed: A002 is not a reproduction and supplies no accepted dependency rate.

What is established

  • PROVED The balanced direct short lift has canonical height O(logp)O(\log p).
  • PROVED The five-coefficient linear lift has height Ok(logp)O_k(\log p) when its constraint matrix has row rank kk modulo pp.
  • EMPIRICAL: three LMFDB values lib/heights.py agrees within 21062\cdot10^{-6}.
  • EMPIRICAL: six primes, three trials each General least-norm logarithmic slopes are 4.543,6.983,8.643,10.3084.543,6.983,8.643,10.308 for k=1,2,3,4k=1,2,3,4.
  • EMPIRICAL: exact p=257 enumeration The paper's Experiment C probability 1/651/65 is reproduced.
  • EMPIRICAL: 108 k=2,3,4 variants No rational relation through coefficient bound eight was found.
  • CITED Jacobson et al. obtain conditional failure from bounded relation coefficients, not a pcp^c height lower bound for selected lifts.

Failed attempt A002

  • CITED The target was Table 3's 317 dependent cases in 100,000 p=17p=17 Experiment A runs.
  • PROVED The source does not fix the sampling/tie-breaking distribution over short projective and coefficient-lattice vectors.
  • EMPIRICAL: local environment on 2026-07-14 The LiDIA/SIMATH and 2-descent pipeline is unavailable.
  • PROVED code/reproduce_xedni_p17.py is a diagnostic prototype only; do not report or compare a rate from it.
  • CONDITIONAL: original code or complete sampling specification plus equivalent 2-descent Reuse the validated lattice and model-conversion components.

Active thread

PROVED A001 corrects the formulation but does not force rational dependence. A002 is dead. The remaining problem is a dependence-conditioned structural theorem or a genuinely faithful historical reproduction.

Next action

Do not rerun A002 as evidence. Resolve Q018 by obtaining the original sampling/2-descent pipeline before reopening SG-09; otherwise work from the exact SG-08 bounded-relation table.

Invariants

  • Use the LMFDB/Sage non-normalized canonical height.
  • Keep rank_status=unavailable until an actual rank computation is run.
  • Say no relation through bound 8, never independent, for SG-08 negatives.
  • State the coefficient-lift sampling rule; least Euclidean norm is a construction bias.
  • Do not infer a positive power exponent from the six-prime range.
  • Do not call A002 a reproduction or use its prototype output as evidence.

Files that matter

  • NOTES.md: proofs, measurements, SG-08 audit, and A002 failure boundary.
  • attempts/A001-explicit-small-lifts.md: successful formulation correction.
  • attempts/A002-p17-experiment-reproduction.md: dead attempt and post-mortem.
  • code/analyze_lift_relations.py: exact bounded-relation audit.
  • data/analyze_lift_relations_b5-7-9-11_B8_allv_20260714_{rows,summary}.csv: SG-08 output.
  • code/reproduce_xedni_p17.py: failed-attempt prototype, reusable components only.
  • refs/jacobson-et-al2000.md: primary-source result and assumptions.
  • OPEN_QUESTIONS.md Q018: exact condition for reopening SG-09.

What I would tell my replacement

PROVED Small simultaneous lifts are easy at fixed kk; the missing xedni ingredient is rational dependence compatible with finite inputs that exclude useful small relations. The exact audit sharpens that distinction, while A002 must remain recorded as a failure unless its missing reproduction inputs are supplied.

2 attempts4 scripts8 datasets2 references