Generalize to a graph-theoretic formulation

This may turn out to be not as much a "proof strategy" as "another interesting way of thinking about the problem", but the hope is to generate examples much more tractable by hand and by computer which reveal graph theoretic properties that force certain discrepancies; and translate those into number theoretic properties we can search for (perhaps very rare ones, but ones we can prove exist nonetheless).

---

(General formulation) Define a set of nodes [math]\displaystyle{ a_1, a_2, ... }[/math] with k sets of directed edges [math]\displaystyle{ e_j = \left \{ e_{j}^1, e_{j}^2, ... \right \} }[/math] (for [math]\displaystyle{ 1 \leq j \leq k }[/math]) such that each set of edges (with corresponding nodes) forms an acyclic path.

Give each node a value of 1 or -1. Consider any traversal corresponding to a set [math]\displaystyle{ e_j }[/math] that starts at the root node; define the absolute value of the sum of the values of the nodes visited to be [math]\displaystyle{ t_j }[/math].

Possible conditions given a set of nodes [math]\displaystyle{ a_1, a_2, ... }[/math] (or the finitary case [math]\displaystyle{ a_1, a_2, ... a_n }[/math]):

No subsets (NS): No set of edges is a subset of another set.

Omega set (OS): One set of edges connects [math]\displaystyle{ a_i }[/math] to [math]\displaystyle{ a_i+1 }[/math] for all i (or in the finitary case, all i from 1 to n-1).

Always increasing (AI): For any edge from [math]\displaystyle{ a_i }[/math] to [math]\displaystyle{ a_j }[/math], i is less than j.

Isolated roots (IR): Each node can be the root node of only one set of edges. [This condition is needed for the definition of completely multiplicative.]

---

Define an infinite set of nodes [math]\displaystyle{ a_1, a_2, ... }[/math] such that given a node [math]\displaystyle{ a_r }[/math] there is a edge in the set [math]\displaystyle{ e_r }[/math] from [math]\displaystyle{ a_r(n) }[/math] to [math]\displaystyle{ a_r(n+1) }[/math] for all [math]\displaystyle{ n \in \mathbb{N} }[/math].

Asking if there is some fixed C that [math]\displaystyle{ t_j }[/math] is always bounded by is equivalent to our problem.

---

Here is a possible meaning for “completely multiplicative”, although it is extremely messy and could likely be simplified.

Define everything as above, including the 5 extra conditions.

Call the set of edges from condition #1 the omega set, and the root node of that set to be the alpha node.

A node is called prime if the in-degree is 1; that is, the only edge incoming is from the omega set.

A node is a power if the in-degree is 2.

Consider all incoming edges to a particular node; trace the edges backwards to their root nodes. These are the divisors of the node.

Here is a prime factorization algorithm for the node n:

1. List the k divisors of n (excluding the alpha node) [math]\displaystyle{ d_1, d_2, ... d_k }[/math]. Call the path of a divisor to be the traversal going from the divisor to n. Given any divisor a that has divisor b in its path, remove a from the list.

2a. If n is already a power, jump to 2c.

2b. For any divisor that is not prime and is not a power on the list [math]\displaystyle{ d_1, d_2, ... d_k }[/math], connect the divisors of each of [math]\displaystyle{ d_1, d_2, ... d_k }[/math] as a branching tree (again excluding the alpha node); again, given any divisor a that has divisor b in its path, remove a from the list.

2c. For any divisor that is a power on the list [math]\displaystyle{ d_1, d_2, ... d_k }[/math], connect the divisor that is not the alpha node c a multiple number of times m+1, where m is the number of times powers occur in the traversal between the divisor of c and c.

3. Repeat #2a-c until all divisors on the bottom of the tree are prime.

4. The set of divisors at the bottom of the tree is the prime factorization of n.

So, a graph is completely multiplicative if that multiplying the values of all the nodes in the prime factorization of a node n (including repeated nodes as ncessary) gives the value of the node n.

--

Potential questions: Given a discrepancy d, what is a minimal graph (in terms of nodes and/or edges) where the discrepancy is greater than d? What conditions cause the discrepancy to “break”?

Using conditions 1-4, the minimal set of nodes where the discrepancy must be greater than 1 is 4.

Proof: Consider every possible set of edges using 3 nodes.

set A: 1->2->3 set B: 1->3

Then [math]\displaystyle{ a_1 = 1 }[/math], [math]\displaystyle{ a_2= -1 }[/math], [math]\displaystyle{ a_3= -1 }[/math] has a discrepancy of 1.

However, consider these sets with 4 nodes:

set A: 1->2->3->4 set B: 1->3 set C: 1->4

Then no combinations of +1 and -1 (set A constrains the possibilities to + – + -, – + + -, + – - +, and – + – +) avoids having a discrepancy of 2 in some set of edges.