"""Exact finite cases in the degree-two early projection argument for Erdos 931.""" from collections import defaultdict from fractions import Fraction from itertools import combinations_with_replacement, product from math import comb def trace_count(n): # Split the first vanishing difference into two short integer sums. coeff = [(-1) ** (n + 1 - j) * comb(n + 1, j) for j in range(n + 2)] split = len(coeff) // 2 left = defaultdict(list) for word in product(range(5), repeat=split): left[sum(a * b for a, b in zip(coeff, word))].append(word) count = 0 for tail in product(range(5), repeat=len(coeff) - split): key = -sum(a * b for a, b in zip(coeff[split:], tail)) for head in left.get(key, ()): values = list(head + tail) while len(values) < 2 * n: start = len(values) - n - 1 val = -sum(coeff[j] * values[start + j] for j in range(n + 1)) if not 0 <= val <= 4: break values.append(val) if len(values) == 2 * n and len(set(values)) > 1: count += 1 return count def root_polynomial(roots): coefficients = [1] for root in roots: coefficients = [a - root * b for a, b in zip([0] + coefficients, coefficients + [0])] return tuple(coefficients) def fibre_candidates(n, length, k): # Indexed first by the common high coefficients, then the varying low ones. groups = defaultdict(lambda: defaultdict(dict)) for roots in combinations_with_replacement(range(k), 2 * n): p = root_polynomial(roots) groups[p[n + 1:]][p[1:n + 1]][p[0]] = roots for group in groups.values(): for low0 in group: for low1 in group: if low1 <= low0: # constant trace, or reversed order of the late labels continue lows = [tuple(a + h * (b - a) for a, b in zip(low0, low1)) for h in range(length)] if any(low not in group for low in lows[2:]): continue for c0, c1, c2 in product(*(group[low] for low in lows[:3])): step = c0 + c2 - 2 * c1 if not step: continue constants = [c0 + h * (c1 - c0) + step * comb(h, 2) for h in range(length)] if any(c not in group[low] for c, low in zip(constants, lows)): continue fibres = tuple(group[low][c] for c, low in zip(constants, lows)) scale = Fraction(2, step) trace = [1 + scale * (c0 - c1)] + [ scale * (a - b) for a, b in zip(low0, low1) ] for v in range(k): labels = [h for h, roots in enumerate(fibres) if v in roots] if len(labels) not in (1, 2): break total = sum(a * v ** j for j, a in enumerate(trace)) if total != sum(labels) * (2 // len(labels)): break else: yield n, length, k, scale, tuple(trace), fibres if __name__ == "__main__": counts = tuple(trace_count(n) for n in range(2, 11)) assert counts == (36, 22, 8, 0, 0, 0, 0, 0, 0), counts print("Nonconstant traces on the first 2n nodes for n=2 through 10:", counts) candidates = [] for n, length in [(2, 3), (2, 4), (2, 5), (2, 6), (3, 3), (3, 4), (4, 3)]: for k in range(n * (length - 1), n * length + 2): candidates.extend(fibre_candidates(n, length, k)) expected = (2, 3, 4, Fraction(1, 2), (3, -3, 1), ((1, 1, 2, 2), (0, 1, 2, 3), (0, 0, 3, 3))) assert candidates == [expected], candidates print("Sole candidate up to late-grid reflection:", candidates[0])