erdos-unit-distance: Certified Unit-Distance Graphs and Point Sets

Generate and verify finite unit-distance point sets and unit distance graphs for discrete geometry in Rust and Python. Includes the Moser spindle, square and triangular grids, and certified multiquadratic constructions inspired by the Erdős/Erdos unit-distance breakthrough.

The first supported production target is a finite Section 2 multiquadratic construction. The crate does not claim to implement the full class-field tower proof. Exact certificate data is authoritative; floating-point coordinates are for application output, visualization, export, and independent numerical audit.

Use Cases

Generate unit-distance graphs for algorithm experiments.
Build certified finite point sets for discrete geometry applications.
Reproduce Moser spindle, square grid, and triangular grid examples.
Export geometry to CSV, SVG, or OBJ.
Verify construction certificates independently from floating-point output.

Rust Quick Start

use erdos_unit_distance::{MultiquadraticConfig, UnitDistanceSet};

fn main() -> Result<(), Box<dyn std::error::Error>> {
    let config = MultiquadraticConfig::builder(vec![5, 17], 101, 1).build()?;
    let set = UnitDistanceSet::multiquadratic(config);
    let certified = set.generate_certified(100)?;
    let report = certified.verify()?;

    println!(
        "{} points, {} certified construction edges, {} floating audit edges",
        report.point_count, report.certified_edge_count, report.audit_edge_count
    );
    Ok(())
}

Python Quick Start

import erdos_unit_distance

certified = erdos_unit_distance.generate_multiquadratic_certified(
    generators=[5, 17],
    split_prime=101,
    k=1,
    n_target=100,
)

assert certified["verified"]
print(certified["point_count"], certified["certified_edge_count"])

Correctness Contract

Classical constructors are deterministic finite point sets.
Multiquadratic construction validates generators, split primes, and search parameters before generation.
Exact rational algebraic elements drive construction state, candidate paths, norm-one translation checks, deduplication keys, and certified construction edges.
CertifiedPointSet::verify() verifies the exact construction certificate and then verifies the separate floating audit report against projected points.
FloatingAuditReport is numerical and tolerance-based. It is useful for application inspection, but it is not the proof object.
Unsupported class groups, ideals, and tower machinery are not hidden behind production APIs.

More detail: docs/correctness-contract.md.

Supported APIs

Rust:

UnitDistanceSet::moser_spindle()
UnitDistanceSet::square_grid(rows, cols)
UnitDistanceSet::triangular_grid()
MultiquadraticConfig::builder(generators, split_prime, k)
UnitDistanceSet::multiquadratic(config)
generate_points(n)
generate_certified(n)

Python:

generate_moser_spindle()
generate_square_grid(rows, cols)
generate_triangular_grid(n)
generate_multiquadratic(generators, split_prime, k, n_target)
generate_multiquadratic_certified(...)

Verification

./scripts/check-format.sh
./scripts/check-clippy-strict.sh
./scripts/check-tests.sh
./scripts/check-doctests.sh
./scripts/check-examples.sh
./scripts/check-bench-compile.sh
./scripts/check-python-smoke.sh

Run everything locally with ./scripts/check-all.sh.

Run real Criterion benchmarks with:

./scripts/bench.sh

Paper Traceability

docs/paper-map.md tracks what is implemented from the proof and what remains external-backend or future work.

License

Licensed under either Apache-2.0 or MIT, at your option.

erdos-unit-distance 0.1.0