# Computer proof that completely multiplicative sequences have discrepancy greater than 2

(diff) ← Older revision | Latest revision (diff) | Newer revision → (diff)

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.