Computer proof that completely multiplicative sequences have discrepancy greater than 2

From Polymath Wiki
Revision as of 23:09, 1 February 2010 by Teorth (Talk | contribs)

(diff) ← Older revision | Latest revision (diff) | Newer revision → (diff)
Jump to: navigation, search

The following |C code implements this algorithm for making deductions about multiplicative functions of discrepancy 2. At any given time, the "knowledge" that this algorithm has is given by:

  • a reduced expression for f(n) for each n, of the form f(n) = +f(m) or f(n)=-f(m). Thus for instance if we know that f(2)=-1, then we can reduce f(12)=-f(3). This is recorded by an array vals, thus for instance vals[12]=-3 would be recording the fact that f(12)=-f(3).
  • Upper and lower bounds for each of the partial sums f[1,n] := f(1)+...+f(n).

The "easy" deductions that the algorithm makes automatically are:

  • consequences of multiplicativity (e.g. f(n^2)=1);
  • Adjusting upper and lower bounds for f[1,n] based on knowledge of f[1,n-1] and f(n), or of f[1,n+1] and f(n+1);
  • Deducing the value of f(n) given enough information about f[1,n] and f[1,n-1]

After running the initialisation routine init(), there are three main routines:

  • set(p,s): this forces f(p)=s
  • deduce(): run all the easy deductions available from the current state of knowledge; halt if an error occurs and display the current state
  • display(): display the current state.