 |
| Constraint and Consequence |
|
|
 | |
| Craig Holman Research Jabberwocky Quotations Contact | |
Home >
Jabberwocky 
Next
|
|
| |
Jabberwocky for May 26, 2008 |
|
IsaiahI'm starting this blog on the birthday of my partner, Isaiah. I miss him.An alternative version of the Riemann HypothesisI've read John Derbyshire's book on the Riemann Hypothesis, Prime Obsession, several times with great pleasure. I learned there of an alternate version of the hypothesis that resonants with my mind better than the original.This alternative goes by the name of Denjoy's Probablistic Interpretation. Littlewood proved that this alternate hypothesis is equivalent to the Riemann Hypothesis. Derbyshire's presentation of this approach is adapted from that of Dennis Hejhal. Hejhal's presentation starts with a sequence of coin flips, such as "HTTHTHTHHHHTHTHHTTTH". While the ratio of Heads to Tails approaches 1 as the number of flips increase, the absolute value of the excess of Heads (i.e. Heads - Tails) grows and is, in fact, O(N1/2 + epsilon). Each integer N greater than 1 has a unique prime factorization. Prime p occurs zero or more times as a prime factor of N. If p occurs twice as a factor of N, it is said to be a 'square' factor. If N's prime factorization contains no more than one factor for any prime, it is said to be 'square-free'. The Mobius function mu over the natural numbers is defined as follows: Mobius(1) = 0; for N > 1, Mobius(N) = -1 if N is square free and has an odd number of prime factors, Mobius(N) = 1 if N is square free and has an even number of prime factor, Mobius(N) = 0 if N is not square free. Merten's function M over the natural numbers is defined as follows: M(N) = the sum of Mobius(i) for i in [1..N]. Merten's is simply the accumulation of Mobius. Littlewood proved that the hypothesis that Merten's function is also O(N(1/2) + epsilon) is equivalent to the Riemann Hypothesis. I'll refer to this alternative hypothesis as Littlewood's Alternative for convenience and out of respect. For further information on this approach, please see pp. 322 to 323 of Derbyshire's book (paperback edition). Littlewood's Alternative, a prime representational number system, and blocksI found Littlewood's Alternative enticing and approachable. I've been thinking about it for several years. The following table shows N, Mobius(N), and Merten's(N) for 2 through 50:
N Mu M
2 -1 -1
3 -1 -2
4 0 -2
5 -1 -3
6 1 -2
7 -1 -3
8 0 -3
9 0 -3
10 1 -2
11 -1 -3
12 0 -3
13 -1 -4
14 1 -3
15 1 -2
16 0 -2
17 -1 -3
18 0 -3
19 -1 -4
20 0 -4
21 1 -3
22 1 -2
23 -1 -3
24 0 -3
25 0 -3
26 1 -2
27 0 -2
28 0 -2
29 -1 -3
30 -1 -4
31 -1 -5
32 0 -5
33 1 -4
34 1 -3
35 1 -2
36 0 -2
37 -1 -3
38 1 -2
39 1 -1
40 0 -1
41 -1 -2
42 -1 -3
43 -1 -4
44 0 -4
45 0 -4
46 1 -3
47 -1 -4
48 0 -4
49 0 -4
50 0 -4
M can be seen to meander without apparent reason. I hoped that constraints on M's meandering could be established by investigating subsequences of the square-free natural numbers. I decided to construct these subsequences based upon the largest prime factor of a number. Let the k-th block consist of those square-free integers that have the k-th prime as their largest prime factor (with 2 being the first prime). I decided to use a prime representational system for these integers, in which each column corresponds to a prime number rather than the power of a base, and a 0 or 1 in the i-th column from the right indicates whether the i-th prime is a prime factor of the number. I'll refer to this number system as 'prime representation'. For example, the number '101001' in this system is the product of 2, 7, and 13 and is a representation of 182. The numbers that are members of block k are easily generated - there are 2k-1 four-digit binary numbers that have a '1' as their left-most digit. Each of these binary numbers can be interpreted as the prime representation of an integer. Let's consider block 5. The first column is the prime representation of a square-free integer N, the second column is N, the third column is Mobius(N), and the fourth column is the accumulation of Mobius(N) across teh elements of the block, which I'll refer to as Theta: Index N Mu Theta 10000 11 -1 -1 10001 22 1 0 10010 33 1 1 10011 66 -1 0 10100 55 1 1 10101 110 -1 0 10110 165 -1 -1 10111 330 1 0 11000 77 1 1 11001 154 -1 0 11010 231 -1 -1 11011 462 1 0 11100 385 -1 -1 11101 770 1 0 11110 1155 1 1 11111 2310 -1 0 Some observations:
Here is block 5 in 'natural-order', sorted by N, having the same columns as the previous example: Index N Mu Theta 10000 11 -1 -1 10001 22 1 0 10010 33 1 1 10100 55 1 2 10011 66 -1 1 11000 77 1 2 10101 110 -1 1 10110 165 -1 0 11001 154 -1 -1 11010 231 -1 -2 10111 330 1 -1 11100 385 -1 -2 11011 462 1 -1 11101 770 1 0 11110 1155 1 1 11111 2310 -1 0 Note that, when the numbers in block 5 are sorted into natural order, Theta is no longer constrained to [-1, 1]. We can think of Theta as a block-level Merten's. Theta is the contribution to Merten's by the numbers in a block. Note that the Theta function for a block is dependent upon how the numbers in the block are ordered. Let's consider blocks 4 and 5 in binary-index order: Index N Mu Theta 1000 7 -1 -1 1001 14 1 0 1010 21 1 1 1011 35 1 2 1100 42 -1 1 1101 70 -1 0 1110 105 -1 -1 1111 210 1 0 10000 11 -1 -1 10001 22 1 0 10010 33 1 1 10011 66 -1 0 10100 55 1 1 10101 110 -1 0 10110 165 -1 -1 10111 330 1 0 11000 77 1 1 11001 154 -1 0 11010 231 -1 -1 11011 462 1 0 11100 385 -1 -1 11101 770 1 0 11110 1155 1 1 11111 2310 -1 0 Note that the binary indices of block 5 are built up of two modified copies of those of block 4, one following the other. The sign of Mu depends upon the number of prime factors, i.e. the number of 1's in the binary index. The first modified copy of the indices of block 4 has a 0 inserted after the leading 1 - this additional 0 does not affect the value of Mu. The second modified copy of the indices of block 4 has a 1 inserted after the leading 1 - this additional 1 flips the sign of Mu. This pattern for Mu holds for all blocks k-1 and k, k > 0. I assert the following (to be proven later):
Some more observations:
Here's some information on the first six blocks. Be forewarned that the information on a row generally involves more than one N. Columns 3 and 4 are for block elements in natural order. Each value in column 4, labeled 'S', is the sign of Mobius(N) for the value of N in column 3. Columns 5 and 6 are for block elements in binary-index order. Each value in column 6, labeled 'S', is the sign of Mobius(N) for the value of N in column 5. Column 7 is the position delta, the difference in position, between elements of the block in natural order and in binary-index order. It reflects how much each element 'moves' as the block order is changed from binary-index to natural. Column 8 contains the values of Theta for blocks in natural order.
1 2 3 4 5 6 7 8
N N Position
Block Index Natural S Index S Delta Theta
1 1 2 - 0 -1
2 10 3 - 3 - 0 -1
2 11 6 + 6 + 0 0
3 100 5 - 5 - 0 -1
3 101 10 + 10 + 0 0
3 110 15 + 15 + 0 1
3 111 30 - 30 - 0 0
4 1000 7 - 7 - 0 -1
4 1001 14 + 14 + 0 0
4 1010 21 + 21 + 0 1
4 1011 42 - 35 + -1 2
4 1100 35 + 42 - 1 1
4 1101 70 - 70 - 0 0
4 1110 105 - 105 - 0 -1
4 1111 210 + 210 + 0 0
5 10000 11 - 11 - 0 -1
5 10001 22 + 22 + 0 0
5 10010 33 + 33 + 0 1
5 10011 66 - 55 + -1 2
5 10100 55 + 66 - 1 1
5 10101 110 - 77 + -3 2
5 10110 165 - 110 - 1 1
5 10111 330 + 154 - -2 0
5 11000 77 + 165 - 2 -1
5 11001 154 - 231 - -1 -2
5 11010 231 - 330 + 3 -1
5 11011 462 + 385 - -1 -2
5 11100 385 - 462 + 1 -1
5 11101 770 + 770 + 0 0
5 11110 1155 + 1155 + 0 1
5 11111 2310 - 2310 - 0 0
6 100000 13 - 13 - 0 -1
6 100001 26 + 26 + 0 0
6 100010 39 + 39 + 0 1
6 100011 78 - 65 + -1 2
6 100100 65 + 78 - 1 1
6 100101 130 - 91 + -3 2
6 100110 195 - 130 - 1 1
6 100111 390 + 143 + -9 2
6 101000 91 + 182 - -1 1
6 101001 182 - 195 - 3 0
6 101010 273 - 273 - 0 -1
6 101011 546 + 286 - -6 -2
6 101100 455 - 390 + 5 -1
6 101101 910 + 429 - -5 -2
6 101110 1365 + 455 - 2 -3
6 101111 2730 - 546 + 4 -2
6 110000 143 + 715 - -4 -3
6 110001 286 - 858 + -2 -2
6 110010 429 - 910 + 5 -1
6 110011 858 + 1001 - -5 -2
6 110100 715 - 1365 + 6 -1
6 110101 1430 + 1430 + 0 0
6 110110 2145 + 2002 + -3 1
6 110111 4290 - 2145 + 1 2
6 111000 1001 - 2730 - 9 1
6 111001 2002 + 3003 + -1 2
6 111010 3003 + 4290 - 3 1
6 111011 6006 - 5005 + -1 2
6 111100 5005 + 6006 - 1 1
6 111101 10010 - 10010 - 0 0
6 111110 15015 - 15015 - 0 -1
6 111111 30030 + 30030 + 0 0
File of information on blocks 1 through 9 It is much easier to see the structure of the Theta function for naturally ordered blocks when the values for Theta are plotted. |
| Block 4 |  |
|
| Block 5 |  |
|
| Block 6 |  |
|
| Block 7 |  |
|
| Block 8 |  |
|
| Block 9 |  |
|
|
Some observations:
So what? Where do we go from here?
The attack that I propose on the Riemann Hypothesis is prove that Merten's is constrained to be O(N1/2 + epsilon) by proving that the interleaving of the contributions to Merten's by each block is sufficiently destructive that Merten's can not violate the O(N1/2 + epsilon) requirement. Not having solid ideas on how to accomplish this at the moment, I'll move on to describe a new problem. Maximal CliquesThis is a lovely problem in graph theory. Given a graph G, list each of the maximal cliques of G. We need to get a few ideas down before this may make sense. A graph is a set of nodes (dots) and edges (lines that each connect a pair of dots). The graphs that we concerned with are strict graphs - they do not contain any loop edges (connecting a node with itself) or multiedges (more than one edge connecting the same pair of nodes). Another name for 'node' is 'vertex'. The set of vertices of a graph G is denoted by V(G). A graph H is a subgraph of graph G iff every node in H is a node in G and there is an edge between nodes X and Y in H iff there is an edge between nodes X and Y in G. A clique C of graph G is a subgraph of G such that every pair of nodes in C is connected by an edge. A clique that contains k nodes is called a 'k-clique' We'll say that clique A contains clique B if B is a subgraph of A. A clique of G that is not contained in any other clique of G is called a maximal clique of G. Our problem, then, is to identify and list each of the maximal cliques of a graph. One representation of a graph that I like to use is list of augmented adjacency sets. Nodes are numbered 0 to N-1, each node has a slot in the list, and the set in slot k is the set of nodes that are adjacent to (have an edge with) node k. The only twist in this is that I add k to this list (this is the augmentation). We know that k isn't adjacent to itself, but this trick makes it easier to do set calculations. Here is an example of a graph and its list of maximal cliques:
|
Augmented Adjacency Sets for Graph
0 : { 0, 1, 2, 3, 6, 7, 10, 11, 13, 14 }
1 : { 0, 1, 3, 7, 9, 10, 12, 14 }
2 : { 0, 2, 3, 5, 6, 10, 11 }
3 : { 0, 1, 2, 3, 5, 6, 7, 10, 12, 13, 14 }
4 : { 4, 5, 7, 8, 9, 10, 13 }
5 : { 2, 3, 4, 5, 6, 7, 9, 10, 11, 13 }
6 : { 0, 2, 3, 5, 6, 7, 8, 12, 13, 14 }
7 : { 0, 1, 3, 4, 5, 6, 7, 10, 11, 12, 13, 14 }
8 : { 4, 6, 8, 11, 12, 13, 14 }
9 : { 1, 4, 5, 9, 14 }
10 : { 0, 1, 2, 3, 4, 5, 7, 10, 12, 13, 14 }
11 : { 0, 2, 5, 7, 8, 11, 13 }
12 : { 1, 3, 6, 7, 8, 10, 12 }
13 : { 0, 3, 4, 5, 6, 7, 8, 10, 11, 13 }
14 : { 0, 1, 3, 6, 7, 8, 9, 10, 14 }
Maximal 6-cliques
{ 0, 1, 3, 7, 10, 14 }
Maximal 5-cliques
{ 0, 3, 6, 7, 13 }
{ 0, 3, 7, 10, 13 }
{ 0, 3, 6, 7, 14 }
{ 1, 3, 7, 10, 12 }
{ 3, 5, 7, 10, 13 }
{ 3, 5, 6, 7, 13 }
{ 4, 5, 7, 10, 13 }
Maximal 4-cliques
{ 0, 2, 3, 6 }
{ 0, 2, 3, 10 }
{ 0, 7, 11, 13 }
{ 2, 3, 5, 6 }
{ 2, 3, 5, 10 }
{ 3, 6, 7, 12 }
{ 5, 7, 11, 13 }
Maximal 3-cliques
{ 0, 2, 11 }
{ 1, 9, 14 }
{ 2, 5, 11 }
{ 4, 5, 9 }
{ 4, 8, 13 }
{ 6, 8, 12 }
{ 6, 8, 13 }
{ 6, 8, 14 }
{ 8, 11, 13 }
The list of the maximal cliques of a graph can be quite large. The original graph can be reconstructed from the list of its maximal cliques. This means that the list of the maximal cliques of a graph is another representation of the graph, just as the list of the augmented adjacency sets is a representation of the graph. Identifying the maximal cliques of a graph is known to be a difficult problem. I'll talk about its complexity and some of its applications in later posts, but I'd like to get to my algorithm for the problem quickly. My algorithm is based upon what I call the Split Approach. The Split ApproachThe split approach is of use in several of the clique problems in graph theory.Let the augmented adjacency set of a vertex A in a graph G consist of A and all vertices in G that are adjacent to A. Denote this set as AAS(A). The set of augmented adjacency sets for the vertices in G is a representation of G. In addition to speaking of the edges of G, we'll also speak of the non-edges of G, by which we mean the edges of the complement of G. A clique of a graph will be represented as the set of vertices of the clique. There are two key observations that lead to this approach:
For example, let S = { a, b, c, d, e } be a subset of V(G). Let (b, c) be a non-edge of G. S can not be a clique of G because it contains both end-vertices of a non-edge of G. No subset of V(G) that contains both b and c can be a clique of G. We can construct two subsets of S by splitting b from c:
Subset Sx is constructed by removing x from S. All of the cliques of G that are subsets of S are also subsets of Sb or Sc or both. We may construct the set of all cliques of G as follows:
The resulting set CliqueCandidates will contain all of the maximal cliques of G. Variations on this approach can be used to address the following problems:
|
Towards a Maximal Cliques algorithmWhile the set of the cliques of graph G constructed by the split approach constructs does contain all of the maximal cliques of G, it also most likely contains many cliques that are not maximal. We need to do better. We're after a purification process that, in effect, burns away sets of nodes that do not represent the maximal cliques of a graph. Central to this process is an object representing a set of maximal sets from which we can remove sets, to which we can add sets, and which automatically discards sets that are subsets of sets in its collection. The MaximalSetSet class does most of the work in this algorithm and I'll spend some time later discussing it in detail. I'll refer to an instance of a MaximalSetSet class as a reactor. A MaximalSetSet object has a retention threshold, which is the cardinality of the smallest set that is allowed to be retained by the object. The object initially contains no sets. When the object is asked to add a set to its collection, it first determines whether the new set is a subset of set in its collection. If so, the new set is discarded; if not, the new set is added to the collection and the object then identifies and removes any sets in its collection that are subsets of the new set. New sets that have lower cardinality than the retention threshold are discarded. A MaximalSetSet object always ensures that each set in its collection is a maximal set, i.e. not a subset of any other set in the collection. For the maximal cliques algorithm, the retention threshold for MaximalSetSet objects will be set to 1 - every maximal clique should be retained. For algorithms for some other problems (e.g. k-Clique Exists), the retention threshold will increase during the course of the algorithm. When a MaximalSetSet object is told to increase its retention threshold, it sets the new threshold and discards all sets having cardinality below that threshold. Our first task is to construct a list of seed sets, which are initially copies of the augmented adjacency sets of the graph. We'll be 'solving' nodes one by one, constructing a reactor of maximal clique candidates from that node's seed set for each node. Once a node has been solved, all maximal cliques in which it participates have been identified and that node can be removed from consideration when solving other nodes. Thus, when a node has been solved, it can be removed from the seed set for all nodes that haven't yet been solved. The construction of a seed set may be accomplished by intersecting an augmented adjacency set with the set of values in the range ( node .. numNodes - 1 ). One basic task is to pick a node that hasn't yet been 'solved', add its augmented adjacency set to an empty reactor, and use each of the non-edges of the graph to split the sets in the reactor. The sets that are left in the reactor at the end of this task are candidates for maximal cliques - none of them contains both end-nodes of a non-edge of the graph, but we don't yet know whether they are subsets of the maximal clique candidates that are identified by 'solving' other nodes. One method of MaximalSetSet is RemoveSplittableSets, which takes the two end-nodes of a non-edge as parameters and retrieves all of the sets in its collection that contain both of these end-nodes, removing the retrieved sets from its collection. Here is pseudocode for a first approach for accomplishing this task:
Version 1
SplitCompletely( in Set seedSet,
in list<NonEdge> nonEdges
out MaximalSetSet maximalCliqueCandidates )
{
maximalCliqueCandiates.AddSet( seedSet );
foreach ( nonEdge in nonEdges )
{
vector<Set> splittableSets;
maximalCliqueCandidates.RemoveSplittableSets(
splittableSets, nonEdge.Node1, nonEdge.Node2 );
foreach ( splittableSet in splittableSets )
{
Set splitChild1 = splittableSet;
Set splitChild2 = splittableSet
splitChild1.RemoveElement( nonEdge.Node1 );
splitChild2.RemoveElement( nonEdge.Node2 );
maximalCliqueCandidates.AddSet( splitChild1 );
maximalCliqueCandidates.AddSet( splitChild2 );
}
}
}
[Edited on May 30: pseudocode for SplitCompletely was corrected]
One issue that will arise is how many MaximalSetSet objects should be used by an algorithm, and how they should be used. Here are some possibilities:
Another issue involves the candidate consolidation process. It can be accomplished with a single secondary reactor, multiple secondary reactors that get consolidated periodically into a tertiary reactor, etc. Adapting the algorithm so that it makes effective use of multiprocessing will depend on the effective choice of a consolidation strategy. I'm happy to report that the design of a consolidation strategy remains an open problem. Here's some pseudocode for constructing the set of the maximal cliques of a graph. This algorithm makes use of two reactors, one that gets reused for each SplitCompletely call, and a second that is used to gather the results:
Version 1
IdentifyMaximalCliques( in Graph graph,
out vector<Set> maximalCliques )
{
MaximalSetSet nodeMaximalCliqueCandidates;
MaximalSetSet graphMaximalCliqueCandidates;
foreach ( node in graph.Nodes )
{
Set seedSet = graph.AugmentedAdjacencySet( node );
seedSet.IntersectWith( Set.Range( node, graph.NumNodes - 1 ) );
SplitCompletely( seedSet, graph.NonEdges, nodeMaximalCliqueCandidates );
graphMaximalCliqueCandidates.AddSetsStolenFrom(
nodeMaximalCliqueCandidates );
}
graphMaximalCliqueCandidates.RemoveAllSets( maximalCliques );
}
That's enough for today.
Happy birthday, Izzy. |
| |
| Home >
Jabberwocky
Next
|
|
| Craig Holman Research Jabberwocky Quotations Contact | |
| |
| Patterncraft™ and Constraint and Consequence™ are trademarks of Craig Stewart Holman Copyright © 2008 Craig Stewart Holman All Rights Reserved. |
|
| | |
|
|