Theory and Practice

Nearly three decades ago, when I started university all I really wanted to learn was the magic of programming. But my course load included plenty of mathematics and computer theory courses, as well as crazy electives. “What does all this have to do with programming?” I often complained. At first I just wished they’d drop the courses from the curriculum and give me more intensive programming assignments. That’s what I thought I needed to know. In time I realized that most of it was quite useful.

Theory is the backbone of software development work. For a lot of programming tasks you can ignore the theory and just scratch out your own eclectic way of handling the problem, but a strong theoretical background not only makes the work easier it also is more likely to withstand the rigors of the real world. Too often I’ve seen programmers roll their own dysfunctional code to a theoretical problem without first getting a true appreciation of the underlying knowledge. What most often happens is that they flail away at the code, unable to get it to be stable enough to work. If they understood the theory however, not only is the code shorter, but they’d spend way less time banging at it. It makes it easier. Thus for some types of programming, understanding the underlying theory is mandatory. Yes, it’s a small minority of the time, but it’s often the core of the system, where even littlest of problems can be hugely time intensive.

The best known theoretical problem is the ‘halting problem’. Loosely stated, it is impossible to write some code that can determine if some other code will converge on an answer or run forever (however one can write an estimation that works with a finite subset within a Turing Machine and that seems doable).  

In its native form the halting problem isn’t crossed often in practice, but we do see it in other ways. First is that an unbounded loop could run forever. An unbounded recursion can run forever as well. Thus in practice we really don’t want code that is ever unbounded -- infinite loops annoy users and waste resources -- at some point the code has to process a finite set of discrete objects and then terminate. If that isn’t possible, then some protective form of constraint is necessary (although the size should be easily configurable at operational time).

The second way we see it is that we can’t always write code to understand what code is trying to do. In an offbeat way, that limits the types of tools we can use in automation. It would be nice for instance if we could write something that would list out the stack for all possible exceptions in the code with respect to input, but that would require the lister to ‘intelligently’ understand the code enough to know the behavior. We could approx that, but the lack of accuracy might negate the value of the tool.

Another interesting theoretical problem is the Two Generals Problem. This is really just a coordination issue between any two independent entities (computers, threads, processes, etc.). There is no known way to reliability get 100% communication if the entities are independent. You can reduce the window of problems down to a tiny number of instructions, but you can never remove it entirely. With modern computers we can do billions of things within fractions of a second, so even a tiny 2 ms window could result in bugs occurring monthly in a system with a massive number of transactions. Thus what seems like an unlikely occurrence can often turn into a recurring nuisance that irritates everyone.

Locking is closely related to the Two Generals Problem. I’ve seen more bugs in locking than in any other area of modern programming (dangling pointers in C were extremely common in the mid 90s but modern languages mitigated that). It’s not hard to write code to lock resources, but it is very easy to get it wrong. At its heart, it really falls back to a simple principle: to get reliable locking you need a ‘test-and-set’ primitive. That is, in one single uninterrupted single-threaded protected operation, you need to test a variable and set it to ‘taken’ or return that is it unavailable. Once you have that primitive, you can build all other locking mechanisms on top of it. If it’s not atomic however, there will always be a window of failure. That links back to the Two Generals Problem quite nicely, since where it becomes an issue is when you can’t have access to an atomic ‘test-and-set’ primitive (and thus there will always be problems).

Parsing is one of those areas where people often tread carelessly without a theoretical background, and it always ends badly. If you understand the theory and have read works like The Red Dragon Book then belting out a parser is basically a time problem. You just decide what the ‘language’ requires such as LR(1), and how big the language is and then you do the appropriate work, which more often than not is either a recursive descent parser or a table driven one (using tools like lex/yacc or antlr). There are messy bits of course, particularly if you are trying to draft your own new language, but the space is well explored and well documented. In practice however what you see is a lot of crude split/join based top-down disasters, with the occasional regular expression disaster thrown in for fun. Both of those techniques can work with really simple grammars, but then fail miserably when applied to more complex ones. Thus being able to parse a CSV file, does mean you know how to parse something more complex. Bad parsing usually is a huge time sink, and if it’s way off then the only reasonable option is to rewrite it properly. Sometimes it’s just not fixable.

One of my favorite theoretical problems is the rather well-known P vs NP problem. While the verdict is still outstanding on the relationship, it has a huge implication for code optimizations. For people unfamiliar with ‘complexity’, it is really a question of growth. If you have an algorithm that takes 3 seconds to run with 200 inputs, what happens when you give it 400 inputs? With a simple linear algorithm it takes 6 seconds to run. Some algorithms perform worse, so they may take 9 secs (3^2 -- three squared) to run, or even 64 seconds (4^3 -- four to the power of three). We can take any algorithm and calculate its ‘computational complexity’ which will tell us exactly how the time grows with respect to the size of the input. We usually categorize this by the dominant operators so O(1) is a constant growth, O(n) is growing linearly by the size of the input, O(n^c) is growing by a constant exponent (polynomial time) and O(c^n) has the size of the input as the exponent (exponential time). The P in the equation is a reference to polynomial time, while NP is rather loosely any growth such as exponential that is larger (I know, that is a gross oversimplification of NP, but it serves well enough to explain that it references problems that are larger, without getting into what constrains NP itself).

Growth is a really important factor when it comes to designing systems that run efficiently. Ultimately what we’d like is to build is a well-behaved system that runs in testing on a subset of the data, and then to know when it goes into production that the performance characteristics have not changed. The system shouldn’t suddenly grind to a halt when it is being accessed by a real number of users, with a real amount of data. What we’ve learned over the years is that it is really easy to write code where this will happen, so often to get the big industrial stuff working, we have to spend a significant amount of time optimizing the code to perform properly. The work a system has to do is fixed, so the best we can do is find approaches to preserve and reuse the work (memoization) as much as possible. Optimizing code, after its been shown to work, is often crucial to achieving the requirements.

What P != NP is really saying in practice is that there is a very strong bound on just exactly how optimized the code can really be. If it’s not true then there would be no possible way you could take an exponential problem and find clever tricks to get it to run in polynomial time. You can always optimize code, but there might be a physical bound on exactly how fast you can get it. A lot of this work was best explored with respect to sorting and searching, but for large systems it is essential to really understand it if you are going to get good results.

if it were true however, amongst many other implications, that would mean that we are able to calculate some pretty incredible stuff. Moore’s law has always been giving us more hardware to play with, but users have kept pace and are continually asking for processing beyond our current limits. Without that fixed boundary as a limitation, we could write systems that make our modern behemoth's look crude and flaky, and it would require a tiny fraction of the huge effort we put in right now to build them (also it would take a lot of fun out of mathematics according to Gödel).

Memoization as a technique is best known from ‘caching’. Somewhere along the way, caching became the over-popular silver bullet for all performance problems. Caching in essence is simple, but there is significant more depth there than most people realize, and as such it is not uncommon to see systems that are deploying erratic caching to harmful effect. Instead of magically fixing the performance problems, they manage to make them worse and provide a slew of inconsistencies in the results. So you get really stale data, or a collection of data with parts out of sync, slower performance, rampant memory leaks, or just sudden scary freezes in the code that seem unexplainable. Caching, like memory management, threads and pointers is one of those places where ignoring the underlying known concepts is most likely to result in pain, rather than a successful piece of code.

I’m sure there are plenty of other examples. Often when I split programming between ‘systems programming’ and ‘applications programming’ what I am really referring too is that the systems variety requires a decent understanding of the underlying theories. Applications programming needs an understanding of the domain problems, but they can often be documented and passed on to the programmer. For the systems work, the programmer has to really understand what they are writing, for if they don’t, the chances of just randomly striking it lucky and getting the code to work are are nearly infinitesimal. Thus, as I found out over the years, all of those early theory courses that they made me take are actually crucial to being able to build big industrial strength systems. You can always build on someone else’s knowledge, which is fine, but if you dare tread into any deep work, then you need to take it very seriously and do the appropriate homework. I’ve seen a lot of programmers fail to grok that and suffer horribly for their hubris.

Best Practices

One significant problem in software development is not being able to end an argument by pointing to an official reference. Veteran developers acquire considerable knowledge about ‘best practices’ in their careers, but there is no authoritative source for all of this learning. There is no way to know whether a style, technique, approach, algorithm, etc. is well-known, or just a quirk of a very small number of programmers.

I have heard a wide range of different things referred to as best practices, so it’s not unusual to have someone claim that their eclectic practice is more widely adapted than it is. In a sense there is no ‘normal’ in programming, there is such a wide diversification of knowledge and approaches, but there are clearly ways of working that consistently produce better results. Over time we should be converging on a stronger understanding, rather than just continually retrying every possible permutation.

Our not having a standard base of knowledge makes it easier for people from outside the industry to make “claims” of understanding how to develop software. If for instance you can’t point to a reference that says there should be separate development, test and production environments, then it is really hard to talk people out of just using one environment and hacking at it directly. A newbie manager can easily dismiss 3 environments as being too costly and there is no way to convince them otherwise. No doubt it is possible get do everything all on the same machine, it’s just that the chaos is going to extract a serious toll in time and quality, but to people unfamiliar with software development issues like ‘quality’ find that they are not easily digestible.

Another example is that I’ve seen essentials like source code control set up in all manner of weird arrangements, yet most of these variations provide ‘less’ support than the technology can really offer. A well-organized repository not only helps synchronise multiple people, but it also provides insurance for existing releases. Replicating a bug in development is a huge step in being able to fix it, and basing that work on the certainty that the source code is identical between the different environments is crucial.

Schemas in relational databases are another classic area where people easily and often deviate from reasonable usage, and either claim their missteps as known or dismiss the idea that there is only a small window of reasonable ways to set up databases. If you use an RDBMS correctly it is a strong, stable technology. If you don’t, then it becomes a black hole of problems. A normalized schema is easily sharable between different systems, while a quirky one is implicitly tied to a very specific code base. It makes little sense to utilize a sharable resource in a way that isn’t sharable.

Documentation and design are two other areas where people often have very eclectic practices. Given the increasing time-pressures of the industry, there is a wide range of approaches happening out there that swing from ‘none’ to ‘way over the top’, with a lot of developers believing that one extreme or the other is best. Neither too much or too little documentation serves the development, and often documentation isn’t really the end-product, but just necessary steps in a long chain of work that eventually culminates in a version of the system. A complete lack of design is a reliable way to create a ball of mud, but overdoing it can burn resources and lead to serious over-engineering.

Extreme positions are common elsewhere in software as well. I’ve always figured that in their zeal to over-simplify, many people have settled on their own unique minimal subset of black and white rules, but often the underlying problems are really trade-offs that require subtle balancing instead. I’ll often see people crediting K.I.S.S (keep it simple stupid) as the basis for some over-the-top complexity that is clearly counter-productive. They become so focused on simplifying some small aspect of the problem that they lose sight that they’ve made everything else worse.

Since I’ve moved around a lot I’ve encountered a great variety of good and insane opinions about software development. I think it would be helpful if we could consolidate the best of the good ones into some single point of reference. A book would be best, but a wiki might serve better. One single point of reference that can be quoted as needed. No doubt there will be some contradictions, but we should be able to categorize the different practices by family and history.

We do have to be concerned that software development is often hostage to what amounts to pop culture these days. New “trendy” ideas get injected, and it often takes time before people realize that they are essentially defective. My favorite example was Hungarian notation, which has hopefully vanished from most work by now. We need to distinguish between established best practices and upcoming ‘popular’ practices. The former have been around for a long time and have earned their respect. The latter may make it to ‘best’ someday, but they’re still so young that it is really hard to tell yet (and I think more of these new practices are deemed ineffective then promoted to ‘best’ status).

What would definitely help in software development is to be able to sit down with management or rogue programmers and be able to stop a wayward discussion early with a statement like “storing all of the fields in the database as text blobs is not considered by X to be a best practice..., so we’re not going to continue doing it that way”. With that ability, we’d at least be able to look at a code base or an existing project and get some idea of conformity. I would not expect everyone to build things the same way, but rather this would show up projects that deviated way too far to the extremes (and because of that are very likely to fail). After decades, I think it’s time to bring more of what we know together into a usable reference.

What is Complexity?

This is going to be a long and winding post, as there are always fundamental questions that do not have easy or short answers. Complexity is one of those concepts that may seem simple on its surface, but it encompasses a profoundly deep perspective on the nature of our existence. It is paired with simplicity in many aspects, which I wrote about in:

http://theprogrammersparadox.blogspot.ca/2007/12/nature-of-simple.html

It would be helpful in understanding my perspective on complexity to go back and read that older post before reading further.

The first thing I need to establish is that this is my view of complexity. It is inspired by many others, and it may or may not be a common viewpoint, but I’m not going to worry in this posting about getting my facts or references into the text. Instead, I’m just going to give my own intuitive view of complexity and leave it to others to pick out from it what they feel is useful (and to disregard the rest).

Deep down, our universe is composed of particles. Douglas Hofstadter in “I am a Strange Loop” used the term ‘epiphenomenon’ to describe how larger meta-behavior forms on top of this underlying particle system. Particles form molecules, which form chemicals, which form into materials, which we manipulate in our world. There are many ‘layers’ going down between us and particles. Going upwards, we collect together as groups and neighborhoods, based in cities in various regional collections to interact with each other as societies. Each of these layers is another set of discrete ‘elements’ bound together by rules that control their interaction. Sometimes these rules are unbreakable, I’ll call these formal systems. Sometimes they are very malleable: thus informal systems. A deeper explanation can be found here:

http://theprogrammersparadox.blogspot.ca/2011/12/informal-ramble.html

If we were to look at the universe in absolute terms, the sum total of everything we know is one massive complex system. It is so large that I sincerely doubt we know how large it actually is. We can look at any one ‘element’ in this overall system and talk about its ‘context’; basically all of the other elements floating about and any rules that apply to the element. That’s a nice abstract concept, but not very useful given that we can’t cope with the massive scale of the overall system. I’m not even sure that we can grok the number of layers that it has.

Because of this, we narrow down the context to something more intellectually manageable. We pick some ‘layer’ and some subset of elements and rules in which to frame the discussion. So we talk about an element like a ‘country’, and we are focused on what is happening internally in it or we talk about how it interacts with the other countries around it. We can leverage the mathematical terminology ‘with respect to’ -- abbreviated to ‘wrt’ -- for this usage. Thus we can talk about a country wrt global politics or wrt citizen unrest. This constraints the context down to something tangible.

A side-effect of this type of constraint is that we are also drawing a rather concrete border around what is essentially a finite set of particles. If we refer to a country, although there is some ambiguity, we still mean a very explicit set of particles at a particular point in time (inferred).

So what does this view of the world have to do with complexity? The first point is that if we were going to craft a metric for complexity then whatever it is it must be relative. So it is ‘complexity wrt a,b,c,.., z’. That is, some finite encapsulation of both the underlying elements (possibly all the way down to particles or lower) and some finite encapsulation of all of the rules that control their behavior, at every layer specified. Complexity then relates to a specific subsystem, rather than some type of absolute whole. Absolute complexity is rarely what we mean.

In that definition, we then get a pretty strong glimpse of the underpinnings of complexity. We could just take it as some projection based on all of the layers, elements and rules. That is of course a simplification of its essence and that in itself is subject to another set of constraints imposed by the reduction. Combined with the initial subsystem, it is easy to see why any metric for complexity is subject to a considerable number of external factors.

Another harder. but perhaps more accurate way of looking at complexity is as the size of some sort of multidimensional space. In that context we could conceive of what amounts to the equivalent of a ‘volume’, a spatial/temporal approach to looking at the space occupied by the system. This allows use to take two constrained subsystems and roughly size them up against each other. To be able to say that one is more ‘complex’ than the other

Complexity in this way of thinking has some interesting attributes. One of them is that while there is some minimum level of complexity within the subsystem, organization does appear to reduce the overall complexity. That is, in a very simple system, if the rules that bind it are increased, but the increase reduces the interactions of the epiphenomenon, the overall system could be less complex than the original one. There is a still a minimum, you can’t organize it down to nothing, but chaos increases the size of complexity (which is different from the way information theory sees the world). So there is some ‘organizational principle’ which can be used to push down complexity to its minimum, however this principle is still bound by the similar constraints that hold for any restructuring operation like simplicity. That is, things are ‘organized’ wrt some attributes.

Another interesting aspect of this perspective of complexity is how it relates to information. If complexity is elements and rules in layers, information is a path of serialization through these elements, rules and layers. That is, it is a linearized syntactic cross-section of the underlying complexity. It is composed of details and relationships that are interconnected, but flattened. In that sense we can use some aspect of Information Theory to identify attributes of an underlying subsystem. There is an inherent danger in doing this because the path through the complexity isn’t necessarily complete and may contain cycles and overlaps, but it does open the door to another method of navigating the subsystem besides ‘space’. We could also use some compression techniques to show that a particular information path is near a minimal information path. So that the traversal and the underlying subsystem are in essence as tightly woven as they could possibly be.

A key point is that complexity is subject to decomposition. That is, things can appear more or less complex by simply ignoring or adding different parts of the overall complexity. Since we are usually referring to some form of ‘wrt’, then what we are referring to is subject to where we drew these lines in the space. If we move the lines substantially, a different subsystem emerges. Since there are no physical restrictions on partitioning the lines, they are essentially arbitrary.

Subsystem complexities are not mutually independent of the overall complexity. We like to think they are, but in that all things are interrelated. However, there are some influences that are so small that they can be considered negligible. So for instance fluctuations on the temperature of Pluto (the planetiod) are unlikely to affect local city politics. The two seem unrelated, however they both exist in the same system of particles floating about in space, and they are both types of epiphenomenon, although one is composed of natural elements while the other is a rather small group of humans interacting together in a regional confrontation. It is possible (but highly unlikely) that some chunk of Pluto could come crashing down and put an end to both an entire city and any of its internal squabbling. We don’t expect this, but there is no rule forbidding it.

The way we as a species deal with complexity is by partitioning it. We simply ignore what we believe is on the outside of the subsystem and focus on what we can fit within our brains. So we tend to think that things are significantly less complex than they really are, primarily because we have focused on some layer and filtered down the elements and rules. Where we often get into trouble with this is with temporal issues. For a time, two subsystems appear independent, but at some point that changes. This often misleads people into incorrectly assessing the behaviors.

Because we have to constrain complexity, we choose to not deal with large systems, but they still affect the complexity. For the largest absolute overall system, it seems likely that there is a fixed amount of complexity possible. One has to be careful with that assumption though because we already know from Godel’s Incompleteness Theorem that there is essentially an infinite amount of stuff theoretically out there as it related to abstract formal systems. One could get caught up in a discussion about issues like the tangibility of ‘infinite’, but I think I’ll leave that for another post and just state an assumption that there likely appears to be a finite number of particles, a maximum size, an end to time and thus a finite number of interactions possible in the global system. For now we can just assume it is finite.

Because of the sheer size of the overall system, there is effectively no upper limit on how complex things in our world can become. We could apply the opposite of the earlier ‘organizational principle’ to build in, what amounts to artificial complexity and make things more complicated. We could shift the boundaries of the subsystem to make it more complex. We could also add in new abstract layers would again would increase the complexity. It is fairly easy to accomplish, and from our perspective there is effectively an infinite amount of space (wrt a lifetime) to extend into.

One way of dealing with complexity is by encapsulating it. That is cleaving off a subsystem and embedding it in a ‘black box’. This works, so long as the elements and rules within the subsystem are not influenced by things outside of the subsystem in any significant way. This restriction means that working encapsulation is restricted to what are essentially mutually independent parts. While this is similar to how we as people deal internally with complexity, it requires a broader degree of certainty of independence to function correctly. You can not encapsulate human behavior away from the rules governing economies for instance, and these days you cannot encapsulate one economy from any other on the planet, the changes in one are highly likely to affect the other. Encapsulation does work in many physical systems and often in many formal system, but only again wrt elements in the greater subsystem. That is, a set of gears in a machine may be independent of a motor, but both are subject to outside influences, such as being crushed.

Overall, complexity is difficult to define because it is always relative to some constraints and it is inherently woven through layers. We don’t tend to be able to deal with the whole, so we ignore parts and then try to convince ourselves that these parts are not effecting things in any significant way. It is evident from modern societies that we do not collectively deal with complexity very well, and that we certainly can’t deal with all of the epiphenomenon currently interacting on our planet right now. Rather we just define very small artificial subsystems, tweak them and then hope for or claim positive results. Given the vast scale of the overall system, we have no realistic way of confirming that some element or some rule is really and truly outside of what we are dealing with, or that the behavior isn’t localized or subject to scaling issues.

Mastering complexity comes from an ever-increasing stretching of our horizons. We have to accept external influences and move to partition them or accept their interactions. In software, the complexity inherent in the code comes from the environment of development and the environment of operations. Both of these influence the flow and significance of the details within the system. Fluctuations from the outside needs and understanding, drive the types of instructions we are assembling to control the computer. Our internal ‘symbols’ for the physical world align or disconnect with reality based on how well we understand their influences. As such, we are effectively modelling limited aspects of informal systems in the real world with the formal ones in a digital world. Not only is the mapping important, but also the outside subsystems that we use to design and built it. As the boundaries increase, only encapsulation and organization can help control the complexity. They provide footholds into taming the problems. The worst thing we can do with managing complexity is to draw incorrect, artificial lines and then just blind ourselves to things crossing them. Ignoring complexity does not make it go away, it is an elementary property of our existence.

Real Difficulties

I've been Cantoring about set theory for a few posts now and I can't find any obvious inconsistencies. No holes, no places where 135 years of brilliant people pounding on it have left in-roads.

There are aspects of the way set theory handles various infinities that I wonder about, but within the context of set theory itself, it all appears consistent.

Still, this is unsatisfying because it never really answered my questions about infinities. I got curious about the structure of the reals precisely because I couldn't picture any way that a structure could head off to multiple infinities in a way that can't be enumerated. No matter how many infinities, it should be possible to place a finite limit on all of them, and then just parcel them out, one by one.

Well, in that sense it sounds simple. However, when it comes to actually dealing with the infinite paths that make up the real numbers, there does seem to be a few added problems. A few that are surprisingly deep.

Strangely, there is a well-known structure to hold the representations of all of the permutations for R, for which mathematicians agree that it does in fact express all of the possibilities. In A Very Large Structure, I go through the basis of taking one of these base10 real representation trees, called P0 and along with an infinite node parent tree, create a structure T that (in theory) contains all of the real values.

The problem with that post was that given the unknowns in the underlying structure, it is assumed that the constructed sets P0, Pn and T are all uncountable. We can construct the sets, but we cannot count the elements in those sets.

Still, it is a good first step, in that at least R is contained in a set T, and we now have someway of visualizing the different elements in R.


INFINITE CONSTRAINTS

A point that will come up again and again in this post is how to constraint a set of multiple infinite values (on different "axises"). If we do have things stretching off to some large number of different infinities, we can limit each one, and then permute them, one at a time.

In this way, we can count things. An example is being able to count the cells of a bi-infinite spreadsheet, it stretches off into four different directions, on two different axis (vertical and horizontal). We can count the cells by circling around the center, slowly increasing the size of the circle. In a regular spreadsheet that only goes off to the right and to the bottom, we still have two axises, and we can use just diagonals to count everything.

Another example is how I was enumerating the right hand side of the example in the post on Magic Sequences. It's another diagonal example. Yet another example was in the original Infinite Node Tree post. Again, we essentially circle around the inside of the tree, gradually opening the different infinities, one at a time.

It works out that so long as we have some type of 'memory' or stack, we can constrain any number of infinities (even an infinite number of them, it's just more memory), parceling out the elements, one-by-one, and gradually opening up the size of the bounds. There is likely a nice way to prove this, but all on it's own it is mostly self-evident.

And it's exactly this point that keeps driving me to find out why everybody believes that the real values seem to have a way to counter this. The essence of 'uncountable' seems to come not from the structure of thereals, or the number of embedded infinities, but from how they are related to each other in a combinatorial sense.

I kept assuming that the structural attributes would take precedence. After all, if we can pack all of R into some fixed structural representation, then there ought to be a large number of different alternative structures. One of them must be countable.


FUNNY NUMBERS

Another issue that we can deal with early on is this post is that 1.0 = 0.9999... Personally I see this as an abuse of the way infinities work. In the proof listed inWikipedia:

http://en.wikipedia.org/wiki/0.999...

I don't think the subtraction at line 3 in the Digit Manipulation section is particularly valid. The missing difference is caused by a subtle shift in the way the finite representations are being handled. The two infinities are slightly offset from each other. But that's not a popular opinion in mathematical circles.

Another way of looking at this is that the following very small number:

0.000...001 

is considered to be just too small to be a real number. Which is kinda mean, don't you think? I mean, so it is tiny, sure, but does that somehow invalidate its existence?

If we have an example, such as a base10 tree, we see that at any node, at any time, anything can just peel off. Even if it's extremely small. We can go down a near infinite number of zeros, and then just start winding around.

It similar to how we often get junk digits hidden below floating point numbers in a computer after a large series of arithmetic operations. Mostly it is worth ignoring, but in this case while the paths lead to very small numbers, they are still valid paths in the tree, and by (some) definition every path in the tree is a unique number.

Still, if we have a set with:

S = { 1.0, 0.99999... }

we can allow it to be either be two elements or just a single element. Set theory neatly hides this for us.

It makes no real practical difference. Everybody is allowed to have their own viewpoint, and it won't affect the overall results. There is enough space in this area of mathematics to support minuscule-number-haters. :-)

Although I didn't investigate deeply, one would expect that if there is one case of this with little numbers, there are probably an infinitely large number of cases. It should likely be possible to build up a large number of little differences, and prove something horrible like 1=2, or some other fun result like that.


TREE TIPPING

Getting back to reals, if we have all of the reals in a base10 structure, then we should be able to manipulate it. This is a popular place for cranks to start from, because the base10 version seems to be easily complete. The problem with the base10 structures is that they leave the real numbers as endless paths. That makes them more or less impossible to count directly, so we ought to try some funny business.

P0 is our base10 representation tree, over the range [0,1).

We can fiddle with this tree, but I'll switch it to base2 (binary) first because it's a little easier to deal with:

So we have a tree called B2, which is:

- a binary tree
- root is labeled 0
- all children have a left child labeled 0 and a right child labeled 1
- covers the range [0,1)

If we run down an infinite winding path and finesse it into a base2 number, we get:

0.11 0010010000 11111 10110 …

This is actually Pi shifted right twice (Pi/4 ?), so we know this is an infinite string of non-repeating digits.

Now, it is well known that the nodes of a tree are enumerable, but the actual paths themselves are not. Being sort of clever, I first figured that I could just "tip" the tree onto its side, so that the nodes no longer held the representation of the path. Instead, each node could hold a complete infinitely long real value.

If I have such a tree of reals, each completely contained in its own unique node, then I can enumerate all of the nodes, and thus all of them...

Tipping is easy, so long as we have an infinite node tree to tip it into. We just take the far left path:

0.000000000...

As the root node, and then we add in all of it's children. In this case, the children are the infinite list of any nodes that wind off to the right from the above path,ie:

0.100000000...
0.010000000...
0.001000000...
...

Now, for each one of these children, starting with 0.100000... we can add in all of their right children:

0.110000000...
0.101000000...
0.100100000...
...

Etc.

In that way, if we follow the first child down a level, for each level we go, we will get more and more strings of 1.

So now as we approach infinity, we get an infinity large tree, where each node holds an infinitely long real value.

This almost seems like it would work, but there are two very serious problems:

0.1111111111...  is never in the tree.

0.11 00100100001111110110… isn't either.

This happens, because no matter how deep we go, our path is made up of only a finite number of transformations. That is, it is an endless string of all zeros, with some "head" string placed in front by the permutations. 

By definition we essentially get a permanent tail of all zeros. And it is the tail of zeros that keep either of the two above numbers from ever appearing in the tree.

So the numbers:

0.111111111100000000...
0.11 0010010000 1111110110 00000 00000 00000 …

Are in the tree, but the actual infinite right branch and all of the irrationals are not.

Just to recap, if I tip a tree like my P0, from my other article, the irrationals, which where basically the last elements in P0, never make it into the the tipped version of the tree. We can count the new tree, but only because the difficult nodes are missing.

In a sense, this implies that the original base10 representation trees never even really held numbers like Pi/10. Well, they did, because they were defined that way, and we can transfer these numbers to a set P0, but they remain strangely disconnected because of their infinite, and non-repeating tails.


A TALE OF TAILS

Now it turns out that these "tails" are far more difficult then they first appear. They keep coming back to haunt me in different ways.

In fact, the real complication in R being uncountable isn't rooted in the way it goes off to three different infinities all at once, it's really just finding a deterministic way of permuting between the different tails that makes it difficult.

That is, the problem isn't that we can't find a structure large enough to handle the reals, it is that we can't bind them all together in a way to make it easy to get from one to another. We can't find a bridge between them. They are disconnected.

Some interesting things about tails:

- they don't have to go through all of the possible permutations. They can miss some.
- they can repeat a nearly endless number of times, only to peel away at the last second, and still be considered non-repeating.
- they can have any number of little junk bits at the end (if you're not a minuscule-number-hater :-)

Still tails and the permutations on them have some issues:

- finite changes to a tail leave it as an irrational
- infinite, but repeating changes to a tail also leave it as irrational
- irrational changes can leave the tail as either a rational or another irrational
- the difference between two distinct tails is an infinite permutation of an infinite number of changes.

In that last point, we have to make an infinitely large number of small changes to align two distinct tails together, all of the way to infinity. Pi/10 -sqrt(2)/10 looks like:

0.314159265...

-.2
+.03
-.003
+.0003
-.00003
-.000008
+.0000001
-.00000001
+.000000001
...

0.141421356...

Where the differences are non-repeating.

To get from one to the other requires an infinite number of changes, stretching all of the way back to the deepest darkest corners of infinity. It would be nice if there were only a finite set of changes between them, but it doesn't work that way. The tails are distinct, and remain so forever.

What is interesting to note from the third point above, is that Pi/10 - sqrt(2)/10 is itself another irrational:

0.172737909...

That is, if we have two independent irrationals, the difference is a third one.


RANDOM CHANCE AND WALKS

A possible way to enumerate the different real values is to bounce around, one at a time, using random numbers. If we just pick randomly from the original base10 representation tree, then maybe our problems go away?

We can get each infinite path from the tree one at a time, by using the following random generation:

0.[0-9][0-9][0-9][0-9][0-9]...

where [0-9] is some random digit between 0 and 9.

For each iteration, we just pick another random number. Since we are picking them one at a time, if as we get to infinity we have a good chance of picking all possible numbers, then we can count them as we pick them.

The big issue is determining whether or not all of the permutations will get selected at some point. When dealing with probabilities like flipping coins, we can always turn to the Law of Large Numbers:

http://en.wikipedia.org/wiki/Law_of_large_numbers

which says that given enough samples, eventually the actual flips will gradually approach the expected value.

That is, if we flip a coin enough, then 50% of the time it will be heads, and 50% of the time it will be tails. In the short run, the percentages may be skewed one way or the other, but eventually they will work out close to the expected value.

Using the law of large numbers we realize that we can get:

- all single random values to be between 0 and 9
- all nodes in the path to be between 0 and 9.
- all all pairs, triplets, etc. to eventually exist for all finite combinations

That seems fine, but again what works for finite problems quickly runs into trouble with infinite ones.

We don't know whether or not we'll get all infinite permutations, and we have no way of working that out. We may miss a few.

That's fatal, because the different between Pi/10 and sqrt(2)/10 is an infinite set of permutations. It's exactly that infinite permutation that we are trying to consistently generate. That's what ties all of the seeds together.

I took a quick look at Markov chains, hoping that might help. If we consider each random path to be a state of some type, and each state to only be dependent on the last one, we can see a random walk through the whole space as a Markov chain.

However, chains with infinite state space, such as this, don't seem to be as well understood, or at least I had trouble finding any reference materials.

Still, you would expect to run into problems trying to calculate probabilities for infinite events. Most of that branch of mathematics seems geared towards finite things, winning game shows, or proving that not everyone can go bankrupt all at once :-) (OK, I admit that's not fair, it was amis-use of actuarial science, or so I was told ...)


SEEDS

What we really have is a large set of independent tails, each belonging to what we can see as discrete seeds with some combintorical relationship between them.

That is, we can start to classify all of the reals as either:

- finite
- repeating
- irrational seed
- the permutation of an irrational seed.

We don't care about the rationals (finite and repeating) because we already know they are easily countable. We know how to step one by one through all of their possible permutations and combinations (we even know how to over-count them :-) They are just included in the base10 structure along with the more difficult irrationals.

To clarify we can define these irrational seeds to be combinatorically independent (algebraically independent?) non-repeating irrational elements, for which there is an infinite number of finite permutations separating any two elements. The term "distinct" is probably an easier way of saying it.


BASIC PERMUTATIONS

In Crank it Up, I built up an infinite spreadsheet with a bunch of simple permutations. The post started with using Pi as the seed, and then applied two different families of permutations on the entries to generate a whole lot of irrationals. Many people pointed out that this was only a slice of the possible reals, but it was interesting anyways because it was a fairly large slice.

Since all of the permutations were either finite, or infinitely repeating, the result of any operations on an irrational is another irrational. That is, so long as there is a definitive pattern to the change, the change itself will not be able to unwind the non-repeating nature of the original number. Non-pattern trumps pattern. Initially that was a bit of a problem, but it can also be beneficial.

We can work out the basic permutations on irrationals as being:

- finite or infinite
- addition/subtraction or multiplication/division
- reconstructive

Using those possibilities, and guessing at a few others, we can define a larger set of different permutations:

- finite changes, example +0.1
- infinite repeating changes, example +0.101010101....
- right/left shift or divide/multiple by 10
- divide/multiple by repeating 0.1010101....
- block swap (re-arrange blocks)

The first three are from the earlier post. The infinite divide is just another possible permutation.

The last change comes from realizing that an irrational with the blocks swapped subtracted from itself will result in a finite number, making the swap itself just a basic permutation.

In fact, this category includes any permutation where the start is an irrational, the finish is an irrational and the difference is a finite set of finite or simply repeating rationals ...

If we take a seed, and apply any finite number of these different types of permutations, the results are a countable set, because we apply them one at a time.

If we apply an infinite number of such permutations, the results are also countable, and countably infinite. An example of this being a countably infinite set is in the bi-infinite spreadsheet. We applied the first three permutations listed above, but by circling around, we can avoid the infinities and gradually count all of the elements.

Strangely, we can apply an infinite number of different combinations of permutations, and assuming that we do so, one at a time, and limit how we span across infinite sets, then the results are still a countably infinite set.

So, there appear to be a finite number of different types of permutations, that can be applied in an infinite number of different ways. And in this way we can generate really large sets of related real numbers from a seed that are all countably infinite by construction.


SEED PERMUTATIONS

Now it's interesting to note that if we subtract two seeds from each other, we either get zero, a finite set of permutations, or we get a new seed. This is true for all of the different operators (+ - / *) on thereals, not just subtraction.

If we get a new seed, we can define this to be a 'seed permutation', not just a basic one.

So if two seeds are related, their difference is either 0, a finite number or a repeating rational. This means that they are combinatorically related in some way, the results of some type of basic permutation, not a seed one.

If not we get a new unique irrational number.

For the operators in R:

- the difference between two seeds is either finite or a seed: A - B = C
- the addition is either finite or a a seed: A + B = D
- the multiplicand is either finite or a seed: A * B = E
- the dividend is either finite or a seed: A / B = F

That is, for Pi/10 and sqrt(2)/10, we get:

0.314159265... - 0.141421356... = 0.172737909...
0.314159265... + 0.141421356... = 0.455580621...
0.314159265... * 0.141421356... = 0.044428829...
0.314159265... / 0.141421356... = 2.221441470...
0.141421356... / 0.314159265... = 0.450158157...

Which is a new set of five different irrationals. When the result is a new irrational then we can consider the permutation type to be a seed permutation. That is, a permutation that allows us to jump from two non-repeating seeds to a new seed.

Now, we know for some types pf permutations that seeds themselves are the sum of the permutations between other seeds. That sense of infinite, likely means that although we can identify a finite set of seed permutations, it may be impossible to identify all of them, since there may actually be an infinite number of different types. But I am not sure about that.

The really big problem is that the seeds are very independent from each other. We can't just apply simple numbers to them to get to the next set of seeds. We must look for permutations from a higher level, that is the types that are needed on the seeds themselves to get to each other.

Some known seed permutations:

- limited symbols (numbers using only 2, 3, ..., 9 symbols)
- cut out finite blocks/add in finite blocks
- cut out infinite repeating blocks/add in repeating blocks
- irrational changes (infinite, non-repeating).
- irrational operations (+ - * / on two independent irrationals). 

Given a few seeds, can we find all of the possible seeds that are between the seeds? It seems likely, since there are ways to permute between some seeds, but it certainly isn't an easy question.

How do we know we've hit all seeds? That is the hardest problem. There are likely some major permutations, seed and basic that I am missing. Still my current set is fairly large and still useful. Is it complete? I think that would take further research.

If we apply seed permutations to a set of countably infinite seeds, then the results are still countably infinite. Because we get a new seed, and we can swap back and forth between them. That means we can take an countably infinite set of seeds and generate a much larger set of seeds that is still countably infinite.


COMBINATORICALLY COMPLETE SETS

Now, we can look at this all from a much higher perspective.

If we apply all the basic permutations, we can construct countably infinite sets that hold large numbers of real values. The bi-infinite spreadsheet is an example of this.

We want to define a 'combinatorically complete' set to mean a set of real numbers, based around a seed(s), and permuted with all of the known, possible general permutations possible, but still being countably infinite by definition. 

Start with an real element E0

We can create:

set C0 as a combinatorically complete set based on E0

Now, since we have a complete set, we apply Cantor's diagonal construction to that set, and it will produce a new value that is not in our original set. That is, Cantor's will act as a bridge and give us an element from some othercombinatorically complete set.

E1 is the new seed from C0 created by Cantor's diagonal construction.

set C1 is from the permutations on E1

We can now combine these two base sets:

CC0 = C0 ∪ C1

Since CC0 is a complete set, we can apply Cantor's again which will produce a new element from outside the set:

E2 is another seed from CC0 create by Cantor's

We can keep this up for the sets:

En, Cn and CCn

Where CCn is:

CCn = CCn-1 ∪ Cn

We can see that this is growing, very fast.

For fun, we can add in applying all of the seed permutations SPn as well, and thus any new Cn sets on any new created seeds. Thus we can create something like:

CCSn = CCSn-1 ∪ CCn ∪ SPn

We can take the union of all of these possibilities, both basic and seed permutations and then apply Cantor's to generate a new seed outside of the initial set. We can keep this up for infinity.

Thus our set CCSn is getting quite large. Of course, we can continue this on indefinitely allowing n to approach infinity.


WHAT'S MISSING

While our rapidly growing union of combinatorically complete sets is growing massively and quickly, it is not sufficient to just assume that it will encompass all of the real values. Instead we need to prove that there are is no E'0 that is left out.

Start with an E'0 that is defined to be missing. We know that we can get to this value by any basic permutation, so we have to include that:

U0 is the combinatorically complete set from E'0

Now, for each E'n in U0, it is possible that some set of values UU will generate E'n when using Cantor's diagonalization construction. Since we are interested in making sure those values are uncountable, we have to consider UU to be a possible pathway to E'0, so, it has to stay outside of CCSn.

UU0 is the set that will generate U0,

But each element in UU0 itself could possibly be generated through a bridge from Cantor's, so we have to really consider

UUn

Now there is always at least one element E'n, not in any UUn, so we have to include all of those values into our uncountable set as well.

We have to be careful that any of the seed permutations will not create a path to E'0 either. So we need to consider:

UUSn = UUSn-1 ∪ UUn ∪ USPn

Now, interestingly enough, because we are working backwards from Cantor's, there is no way of being sure that different subsets ofUUSn don't just generate each other's values. Thus it is possible for UUSn to be infinite, but not growing sufficiently larger like CCSn.

The nature of the two sets is quite different.


TOTAL REMAINING SPACE

While we can create a UUSn, we have a problem. UUSn itself is actually countably infinite because of its construction. We can easily count it.

Still there must be uncountable sets so that means there are a whole series of UUSnm sets which are distinct from each other. That is, there is no bridge between them.

That means that there have to be a whole series of un-related UUnm sets,

R = CCSn ∪ UUSn0 ∪ UUSn1 ∪ ... ∪ UUSnm

Still even that provides a problem, since even an infinite number of UUSnm sets is still countable, and now all of our uncountable values are actually countable in some way. So it must actually be something like

R = CCSn ∪ UUSn0 ∪ UUSn1 ∪ ... ∪ UUSnm ∪ ...

Where that final ... is somehow a way of keeping the first part of R -- which although it is disconnected is still countable -- uncountable in some way.

So, now lets take some element Ek. This element might be in CCSn, if it is, then it is countable.

If not, then it might be in UUSnm, and so it is found and counted.

But if it is in neither, it is in the "..." part, then by definition it belongs together with all of its permutations, and all of the seed permutations as a new setDDSn.

But if DDSn is not equal to or a subset of CCSn, and it is not equal to or a subset of any UUSnm, then it must be another element of UUSnm, because it is disconnected from all of the other UUSnm sets.

Because of that, for all Ek, they must belong to either CCSn or the UUSnm sets, which means that R must be laid out as follows:

R = CCSn ∪ UUSn0 ∪ UUSn1 ∪ ... ∪ UUSnm

This means that there must just be the two different types of sets and nothing else. Since each of these is countably infinite  by definition, and there are a countable number of them, then the union of all of them is also countably infinite.

Now, the construction and countability remains the same, even if we remove using seed permutations. It's also the same if we remove all of the basic permutations and just build up the elements one at time, however it is far easier to understand when it is applied to large 'pools' of dependent elements.


ANOTHER PERSPECTIVE

There is another way to look at this. We can start with a T, which we assume to be uncountable. Within T were the Pn sets, each of which is also assumed to uncountable. That stands to reason, since at least one subset of any uncountable set must be uncountable itself.

But if we follow that subset deconstruction downward, we quickly start to get rid of a lot of elements. That is for a set U that is uncountable, we need a series of subsets:

U0, U1, U2, ..., Un ...

of uncountable subsets, all of the way down to an infinite, but very small subset. However there can be no smallest uncountable set, and certainly there can be no finite set at the bottom of everything.

But, at the very bottom, there must be some set of elements. And they must be brought together in some way to form the larger sets:

..., Un, ..., Cn, ...

That is, there can be no smallest quanta in the system, such that it is countable. But everything has to be built up from something.

If we map this back onto our base10 representation tree, we have this structure that is shooting off to infinity in a large number of paths, and for each path. If we prune some nodes from this tree, this essentially says that whatever is left is essentially isomorphic to the original tree.

That is, no matter how many branches you prune, the tree just grows right back. However, one can guess that we should be able to prune faster than the tree can grow, and as such at some point we'll get down to something that is countable, but if we do, then the entire tree was countable.

Not only that, but if we keep pruing the tree, then there needs to be some sort of 'asymmetry' in the tree that causes its uncountable property.

But the base10 tree is really simple, grows uniform and except for being massive, is not really all that complex. At least, not complex enough to hide some asymmetry that accounts for it being impossible to enumerate.


THE HALLWAY ANALOGY

There is another way to look at base10 structures. It is as if you were standing in a very long hallway. There is a door down at one end, but the other end stretches off to infinity. In the hallway are a clump of wires. As each wire runs down the hallway, it becomes many more wires. That is, the clump of wires in front of you, if you are facing the door, is way smaller than the clump next to you, which is smaller than the clump behind you.

If you reach out and grab the clump of wires, there are a finite number of them, and they can easily be counted. Now, if you take a step backwards, and grab the next clump, there are more wires but still finite in number. As we work our way backwards down the hall, we can count more and more of the wires.

In a sense, a base10 representation tree is a rather fixed structure. Its difficulty comes from the fact that it is what I've been calling 2D. That is, there are two separate types of infinities built into the tree: the number of branches, and the length of the branches themselves. We don't need to enumerate both infinities, we only need to know how many infinite branches there are (or could be).

The problem comes from the idea that branches such as the irrationals are not actually in the tree until latter, but again we're only concerned with counting all of thereals , not just the irrationals. The wires running down the hallway are the parents of both, even if they are not full 'infinite' until much later. We don't need to know how long the wires are, we just need to know how many of these are splitting off to infinity.


SEED PERMUTATIONS

It seems likely that seed permutations should also be able to generate everything. That is, there is only one reason why some complete set of seed permutations shouldn't be able to bridge all of the different seed sets together.  An infinite number of different infinite permutations would a pretty solid reason, but if that isn't the case then we can do all of the generation.

Although the infinitely long tails make the conceptualization more complex, underneath, the relationships between the seeds is not that sophisticated. At least not sophisticated enough to be able to prevent counting, or generation of other seeds.

We do know, for instance that we can fit all of the permutations together into a base10 representation tree. Application of a structure, any structure, implies some type of inter-relationship between the elements.

Possibly we can start with the all of the permutations of symbols, and then add/delete all possible infinite pattern representations into the mix to cover the whole spectrum.

Does a simple cut/diff loop generate a lot of seeds? That is, if we start with Pi, and then randomly remove one digit, and subtract the two numbers we'll get another seed. If we keep this up, how much coverage will we get from such a simple algorithm?

Do permuting between all of the different possibly combinations of symbols generate a lot of seeds? Can we just start with all of the two symbol patterns, and move through each different set of permutations?

We know that any seed may or may not go through a specific set of patterns, and it may end up going through the same patterns over and over again, but in a way that doesn't repeat in the long run. In this sense, we could probably generate a giant dictionary of all possible patterns, and then permute them against each other to generate all possible seeds. Of course, as always the weakness is how to handle the infinitely long nature of the patterns.

It's easy enough to use a few methods to permute an infinite number of seeds, an then use the differences to get an even larger infinite number. Continued on infinitely, this may also likely produce full coverage.

If we can see the base10 representation, then our ability to easily jump from infinite branch to infinite branch should not be that complex.


SUMMARY

Tails and infinite permutations in R are a difficult problem. Not because of the complexity of the structures, not even because of most of it stretches out to infinity.

It's hard because there is some combinatorical independence between the different sets. Still, all we need do is tie it all together with a bridge or two.

Cantor's diagonal construction is defined to find things not in a set, therefore it is the perfect bridge builder between sets. Since it can't fail, and it can be used one at a time, we can bounce from countable set to countable set, forever.

Seed permutations should work as well. There is nothing intrinsically complicated about applying permutations to seeds, they're just not as obvious as the basic permutations.

Things should be countable, especially if they can be contained in a structure of some type. Uncountable implies that there is some type of structure that exists, but isn't representable in some strange way; that we can't navigate around it.

It is the structure that has no structure, which is well, rather odd, is it not?

Prime Perspectives

It all started with a dream about infinity. Well, not just one infinity, but an infinite number of them, spanning out in all directions. A repeating pattern of infinities splitting off from other infinities. It's a simple pattern, but also a very complex one.

It was intriguing enough to compel me to spend some time exploring my thoughts a little deeper. I was captivated by the overall pattern.

Somehow, after playing around a bit, I associated the dream with the underlying structure for natural numbers (originally I though it might be related to the P=NP somehow).

I suspected that the structure for prime numbers was driven by some type of blending of an infinite number of far simpler infinite patterns; where a new complex pattern emerges as each simpler one is merged into the rest.

Prime numbers play an important role in Number Theory -- one of the most elementary branches of mathematics -- yet they are cast in all sorts of different devilish manners. They are surrounded by myths, superstitions and a long history of obsessions.

They draw a lot of attention because they are simple, yet hugely complex.

"Mathematicians have tried in vain to this day to discover some order in the sequence of prime numbers, and we have reason to believe that it is a mystery into which the mind will never penetrate." -- Leonhard Euler

Because they are a basic building block of our numbering system, they affect Computer Science heavily. Computers rely directly on primes for things like security, but also indirectly they affect all of our numeric calculations. They help to build up the intrinsic errors we live with when using a discrete space of digital numbers to represent a continuous space of real ones.

While primes rarely intercede directly on the day-to-day aspects of programming, they are always there, quietly in the background influencing our number crunching, and contributing to our errors.

What follows in this post are various different 'perspectives' I played with while exploring the world of primes. I'm not sure of their value, nor of their novelty. I suspect they've all been played with before in the past, but I've found little direct reference to any of them.

By necessity, this is a long, long blog entry. I could have broken it up into smaller pieces, but I really wanted to get all of the major elements out at the same time. Posting a bunch of smaller entries, all on the same day is essentially the same as posting one big long one, so I opted for keeping the entire work together.


BASE P

Our standard number system is based around 10 symbols, but programmers are long familiar with the convenience of changing the number of symbols we used to represent our numbers. Binary (two symbols) and hexadecimal (16 symbols) provide well-know examples that are frequently used because they make it more transparent to read some properties of the numbers.

Roman numerals too, have their uses. Although there are normally only 7 symbols (14 if you include differentiating symbols with lines over them) in the scheme, it could easily have been extended to use an infinite number of symbols. However, they likely stopped at a finite number because allowing an infinite number of symbols would ensure inconsistencies in usage (everyone would pick different symbols for any that are undefined, and an infinite number means that there will always be some undefined).

Sometimes an alternative perspective on the same old underlying information is an extremely useful place to start exploration.

With that in mind, I started experimenting around with creating another base for the natural numbers. One which is based around having an infinite number of symbols.

In this case I wanted one symbol for each unique prime number. It is best described as the prime base, or 'base P' for short.

For convenience I will picked the symbols a, b, c, d, ... mostly because they help clearly differentiate the various properties of this encoding (but also because they are easier to type into my blog :-)

Using a rather common perspective of ignoring 1 as not being a prime number, I started by assigning the symbol 'a' to the prime 2. Then 'b' to 3, 'c' to 5, etc. Composite numbers are composed of strings of their prime factors, so 'aa' is 4, 'ab' is 6, 'ac' is 10, etc. To round it out, I used an empty string ("") to represent 1, and and the NULL string (or NULL character) for zero.

Thus, in numeric order (and ignoring 0 and 1 for the moment) we get the following sequence for natural numbers:

a  b  aa  c  ab  d  aaa  bb  ac  e  aab  f  ad  ...

which represent the normal base 10 sequence:

2  3  4  5  6  7  8  9  10  11  12  13  ...

All of the strings are 'normalized'. For any two different types of symbols, say a and b, if they are in a string together then the lessor one should always be written first.

Thus 'ba' is invalid and is actually identical to 'ab'. Both strings represent the number 6. Then 'dea' is actually 'ade'. They are the same, it is just that one is not normalized. 


SOME USAGE

There are a few interesting things that show up within base P.

The first most obvious one is that multiplication and division are very straight-forward. They are just string operations: concatenation for multiplication and deletion for division. For instance 42 divided by 6 looks like:

abd / ab = d

A number is divisible by another, if and only if the same symbols appear in both strings. Integer division is just a simple matter of removing some symbols. Testing for common divisors is just a matter of seeing what subset is the same in both strings.

If multiplication and division get really easy and simple in this new base, addition and subtraction become horrific. A few examples:

"" + aa = c

aabb - d = j

Both of these show that the operations of addition and subtraction are extremely non-intuitive. There is no easy way of doing these two operations. Interestingly this seems to be a swap from the finite bases, where summation is more intuitive and multiplication has always required learning some type of lookup tables.

Of all of the interesting things to do with these numbers, one caught my attention right away. It is best described as 'merging' series.

I started with the series:

a  aa  aaa  aaaa  aaaaa  aaaaaa ....

and seeing that as an 'axis' of some type, I crossed it with a similar axis:

b  bb  bbb  bbbb  bbbbb  bbbbbb  ....

Once I sorted these numbers into numerical order they gave me something like:

a  b  aa  ab  aaa  bb  aab  aaaa  abb  aaab  bbb  aaaaa  aabb  ...

When I placed both axises on a Cartesian-like graph, and then drew arrows from each number in the sequence to the next, I got this really interesting 'search' pattern:

This implies that the sequence is working it's way through each and every possible combination of the two axis in base P.

It's an interesting result given that I started out by looking for patterns composed of an infinite number of patterns branching off to infinitely.

This pattern comes from just a pair of infinite patterns, combined. If I start adding in the other axises, one by one, this could easily become a complex and diverse pattern that fully represents our basic number system.


PRIME PRODUCT CHART

Playing around some more, I decided to create a 'chart' with all of the base P strings, ordered numerically.

I placed the natural numbers in base P on the vertical axis, and each prime symbol itself on the horizontal axis. Because I did the original in a spreadsheet, I put the numbers on the vertical axis headed downwards, and the prime symbols on the horizontal axis headed right. But it could have been oriented horizontally as well.

My original table was vertically labeled AxisA, PlaneAB, DimABC, etc. as I was treating each repeating symbol sequence as an axis, and the whole sequence together as a search pattern throughout these various axises, as they get added into the sequence one by one.

While it was interesting chart, it was really noisy and hard to understand. So I simplified it, eventually to D1, D2, D3, etc. And then later to just a, b, c, .... Then I started highlight specific cells to see if I could find a pattern.

It was during the processing of simplifying the chart that I suddenly realized that there was a very simple deterministic pattern that was clearly flowing though all of the entries (I also realized that I had made a few mistakes in my original input).

After looking at it a bit, I simplified it into what I like to call the "Prime Product Chart". It is an easy and simple representation of the frequency and structure of prime numbers in our natural numbering system:

When I looked at the above chart, I knew I was onto something interesting. Instead of the complex patterns within patterns I was looking for, I had stumbled onto something far more simple.

This chart basically marks out each of the prime factors for each number. That is, where the number equals 0 mod P (is divisible by P) for all of the different primes in the columns. When there are no possible factors, a new prime gets created and added into the pattern.

Looking at the columns, we can see a clear and easily repeating pattern where the distance between each of the marks in the columns is the value of the prime itself. This is a pretty strong pattern, and at least indirectly it has been known for thousands of years.

The Greeks first discovered this as the algorithm named "the Sieve of Eratosthenes". It has been a pretty well-tested over the centuries (although historic computers -- even those just over a hundred years ago -- tended to have personal problems, make mistakes, get hungry and take occasional lunch breaks).

The algorithm generates the set of all primes for a fixed range.

It iterates through the series of numbers, marking off those which are known to not be prime. It does so in each iteration by marking off the factors of the last known prime number.

The first pass marks off every other number, the second every third number, the fourth every fifth one, and so on. One pass for each prime number.

In that way, eventually "all" of the factors for "all" of the numbers have been marked off to insure that any and all composite numbers are properly removed. What's left over are prime numbers.

The Prime Product chart makes the algorithm obvious. The chart can actually be interpreted as just listing out each different iteration of the sieve. Each column is one pass through the algorithm, and where each row is unmarked that is where a new prime is created.

The next prime in the algorithm, for the next pass, can always be found by moving forward from the last prime until a row of all unmarked cells is reached. It's a simple deterministic step.

From the chart we can see that the location (or not) of primes is a direct result of how each of these different columns interact with each other. As they gradually align together, new symbols are needed to fill in gaps in the pattern.

In that way, it is clear that primes are not laid out indiscriminately. They fall where they fall because of what is essentially a negation of the Chinese remainder theorem. When the next number has nothing in common with any of the previous symbols, a new symbol is necessary.

Where I marked the cells, I also added in the number of times the same symbol repeats as one of the factors 1, 2, 3, etc. There is clearly another pattern buried here with the number of repeated factors, but so far I haven't done anything fun with it. There were so many other interesting questions to play with first.

Getting back to it, a new prime occurs whenever there are no other possible symbols to fill in. Gaps always keep occurring (even when there are a huge number of existing primes), so that new primes are always added into the mix. The pattern doesn't stop (or even slow down that much). There are clearly an infinite number of primes that will get created.

From this chart we can make some interesting observations.

The well-known case where two primes fall closely together is a fairly obvious consequence of the fact that a lot of the earlier primes start coming closer into phase (being at 0 mod P at the same time), but at some point in the pattern the heavily repetitive factor 2 becomes the only reason that the primes are not one right after another. Thus, it enforces a minimal distance.

We'll also see later that it is entirely likely that any two closely related primes can appear at any location within the number system, e.g., that there are an infinite number of prime pairs.

In a way we can visualize any of the unmarked cells as holes through which new primes might be created, a sort of "filter effect",  but we'll get deeper into that later in the post.

Note that there is an 'a' symbol in every other string in base P (and a 'b' in every third, etc.). So the sieve itself is directly represented in base P.

Another point that will get way more interesting later is that like the two base P sequences I talked about merging earlier in this post, it is clear that the natural numbers go through each and every permutation of all of the currently existing symbols.

That is, for any set of normalized symbols Pa*Pb*...*Pm, where Pa can be the same prime as Pb, there is one and only one corresponding natural number, and there is always only one number.

The numbers in this sense, lay out all possibly permutations for the normalized strings in base P.

 
ROWS AND COLUMNS

As I explored more deeply, I found a number of interesting things about this chart at the row level.

One easy thing is that it is clear that a prime only exists when there are absolutely no other earlier prime factors are available. That is, a prime occurs when none of the lower primes are 0 mod Pn, where Pn is the nth prime less than the new one.

The gcd function finds lines where each parameter P is 0 mod P, so we need an analogous function, possibly called the lowest common non-multiple (lcnm?) such that:

lcnm(v1, v2, v3, ..., vn) -> 0 != mod v1 && 0 != mod v2 && ... && 0 != mod vn

In this way we can say that:

Pn = lcnm(P2, P3, ... Pn-1)

The nth prime is the lowest common non-multiple of all previous prime numbers.

It's an extremely simple functional representation of the nth prime number (although it nicely glosses over the actual complexities of the numbers themselves).

Another thing I noted was that the minimum distance between prime numbers is always 2, since it is the most common factor. Interestedly enough, the maximum distance between primes changes radically. I watched it go up to around 150 for a small set of numbers, but it clearly goes higher. It is an easy assumption that it will grow to an infinitely large size.

That the distance between primes continues to grow is an important property of the structure of primes. Intuitively it tends to lead to incorrect assumptions.

I had always expected that primes are spaced out a lot farther from each other, as the numbers got bigger. From imagination I would have assumed that prime numbers are few and far between at the really high ranges.

But oddly it just isn't like that. They seem far more dense that one would guess. There are a huge number of massive primes. A surprisingly large number. There are problem a few massive ranges of "low density", but those are followed by ranges of more-or-less normal density (high-density) prime numbers.

The prime-counting function (Pi symbol) attempts to calculate a boundary for prime numbers, but the chart itself is also quite useful for showing how constrained and how dense the overall set of primes really is. There are some structural aspects to the chart that can really help illustrate the patterns.

There are always more symbols entering, but the distances are expanding at more or less the same rate. The density of the primes grows rapidly, but over a rapidly growing field of numbers.


PRIME BLOCKS

What is very noticeable in the chart is that for any N prime numbers (or N columns), there is a block (of rows) in the chart that is exactly P1*P2*...*Pn cells in length.

We can call these N by P1*P2*...*Pn structures 'prime blocks'. As each one is essentially a basic building block coming from the Nth prime number.

That is, for the prime 2 the blocks are every other number. For the prime 3, the blocks repeat every 6 cells. For the prime 5 it repeats every 30 (2*3*5) cells.

Within the block, there are essentially two types of primes. Those that are inherently in the definition of the structure (primes <= Pn) and those that are essentially newly created, above or outside the structure.

I will refer to these as internal and external primes.

As we look at larger blocks in the chart, we see that the thickness of the block grows really slowly by one prime each time, while the depth grows really fast, increases at a massive rate by the product of the next prime.

When I first looked at prime blocks, I missed the fact that as the blocks get larger, the external primes repeat themselves more frequently. While the internal primes form a more-or-less deterministic pattern, the interaction of the different frequencies in the external primes makes for an increasingly complex pattern.

The blocks are essentially stretching rapidly, each time we include another prime, a point which is interesting. Important, because although while we've only explicitly calculated N prime numbers, we've actually tested (and  factored) P1*P2*...*Pn numbers.

That is, in the seive algorithm, as we generate larger and larger prime blocks, we get a sort of magnifying effect out into the number system, showing as all of the other related primes within that block.

Another thing to note is that prime blocks are finite structures for a fixed number of N primes. That is, they exist and get replicated over and over again. Some of the higher external primes will extinguish some of the 'possible' lower ones, but only when they have no common factors. In a way, we can see the blocks themselves a type of base 'filter', and then the external primes add another layer on top of that.

Judging by the overall density of primes, the extinguishing effect from external primes is relatively in-frequent, mostly primes that start in one instance of a block have a good chance of staying prime in any of the following instances (a point that I have been waffling on, so it deserves much more investigation).

At the end of every instance of an N block of primes, the last entry, the one at P1*P2* .. *Pn is always a composite number whose that is divisible by every one of the internal block primes. Lets call it the 'last index' number.

In base P that number is:

a  ab  abc  abcd  abcde  abcdef  abcdefg ...

The last index number is interesting because it delineates the end of the block, but also because of the numbers both on both sides of it. Since it is the last number in the first instance of the block, will call the next number the 'block-start' number.

Often in many cases, the block-start number is a prime.

Looking back at the chart we can see that 7 and 31 are very obvious block-start primes. The 6 pattern repeats on a few different primes until it gets cut down by a couple of powers of 5 (an external prime for the 2*3 block).

Now, it is extremely interesting to note that all this time that we have been assuming that 1 is not, by definition, a prime number, but it is a block-start number (shared for all of the blocks).

Initially it might seem like block-start numbers are always prime, since at least they are trivially co-prime with each of the internal prime numbers. However, the external primes easily make the overall structure significantly more complex.

So, for larger blocks, it turns out that block-starts aren't always prime. The smallest example where they are not is 30031, which is a block-start number for 2*3*5*7*11*13 (abcdef), and is divisible by the external primes 59 and 509.

Block-start numbers are also known as Euler Number and have been around for a long time.

My interest in them comes from mistakenly not realizing that some of the externals could actually extinguish them from being prime. This mistake lead to some very excited effort in trying to generate a massive block-start prime (I generated one with 116 million digits using only a home computer and a week's worth of computing). Oddly, while the number may be prime (or it may not), the sheer size of the number makes it hard to prove, one way or another.


MORE ABOUT BLOCKS

A huge question in Number Theory has been to be able to accurately count the total number of prime numbers. Many great mathematicians have thrown themselves at this problem, always with a limited degree of success.

Perhaps the key issue is that the increasing size of the prime blocks makes the actual number of primes vary significantly for each of the block ranges.

There might not be a single function for the whole range, but possibly only ones for each of the the prime-block ranges (and then a limit as the blocks go to infinity).

I figured it was an interesting issue, but really only from the perspective of trying to show that the arrangement of external primes in very high-up ranges wasn't essentially random.

So I tried taking a new look at this problem but only as trying to find the count within a discrete closed range, may actually produce less complex results.

For instance, we can count the number of primes within specific prime blocks:

For block 2: There is one prime (assuming we don't count 1), which is 50%
For block 6: There are 3, which is 50%
For block 30: There are 10, which is 30%
For block 210: There are 46 primes, which is 21.9%
For block 2310:There are 343 primes, which is 14.5%

The percentages start cleanly, but quickly built up to be 'less obvious' numeric patterns. As the blocks grow larger, the numbers look weirder.

Interestingly enough, we know that the Nth block which is P2*...*Pn in size is actually the N-1 block repeated N times.

If we consider the prime-block itself to be a filter of some type, then for each instance of the filter we can work out the total number of "possible" prime numbers allowed in each block (certainly in terms of the previous smaller prime-blocks, if not in terms of some complete formula).

The big problem comes from having to subtract the correct number of external primes that extinguished any of the possible primes.

Although we could calculate the density of the external primes, we need a simple density function that takes into account overlaps (such as 59, and 509, both extinguishing 30031).

I highly suspect that this calculation is possible, but lately I haven't had the time to dig into it.

PRIME GENERATION FORMULAS

Another interesting issue that pops up all of the time is whether or not we could find one single continuous function for calculating prime numbers. For those not familiar with Binet's formula, this may seem like a near impossible task, but we actually been able to take certain classes of complex recursive functions like the Fibonacci sequence, and create functions from them.

It all starts with being able to get some type of recursive definition for the sequence.

Because we can see the structure of the primes, we can write a program to start at one position and find the next one. We can easily write a program to implement the sieve for instance.

Programs (to some degree) share the same expressive level with recursive formulas, so we can write a recursive formula for creating primes.

We start by stating that a prime number comes from the previous prime, plus some "gap" between the two numbers:

Pn = Pn-1 + Gn(Pn-1)

To make things easier, we want to be able to test to see if any number is not equal to zero modulus some prime. Because we want to use this test for recursive purposes, if the number is not 0 mod P, then we return 1, otherwise 0. In this way we can use it as a multiple, to drop out different terms if necessary. I think the following works:

T(x,m) = Ceil ( ( x mod m ) / x )

If x is 0 mod m, then the fraction is 0 / x, which is 0. Otherwise it is 1. With this function in mind, we can create a recursive function that tests a particular column in the chart to see if all of the cells are all != 0 mod Pk, for all Pk:

FTk(x,Pk) = T(x,Pk) + FTk-1(x, Pk-1)

This is a classic tail-end recursion that evaluates to 0 if all of the recursive levels are 0 mods. From here we can then create a function to calculate the gap simply by trying each row, and if it fails, adding one to the result and moving (via recursion) to the next row.

Gk(x) = 1 + T(FTk(x,Pk), 2) * Gk(x+1)

The outer test function T simply forces the results of FTk to be either 1 or 0, pushing us to the next row in the gap.

With a few initial starting values:

G1(x) = 1
G2(x) = Ceil(x mod 2 / x)

FT1(x, 1) = 1
FT2(x,2) = T(x, 2)
FT3(x,3) = T(x,3) + FT2(x,2)

We have a complete recursive representation of prime numbers.

Now, just because we have a recursive representation doesn't mean that we can find a generator function for this, or that we could find a formula for the Nth base prime.

While Binet's formula does work for the recursive Fibonacci series, the difference is in the fact that the recursion in the Fibonacci sequence is simple (and not entirely necessary, although it is the easiest way to see it). The recursion in the prime number formula is extremely complex and self-referential.

Oddly, it all comes down some issues about information. Although it's not explicit, the Fibonacci sequence contains within its composition a structure that can be represented in multiple ways. Once by a simple recursive function, and again by a more complex one for the Nth number that is based on golden ratios. Although the secondary representation is far from obvious, the "information" to make it work is implicit with the recursive formula and the number system itself (in the same sense that many computer programs depend heavily on the operating system to be complete).

Since it was non-intuitive, it certain opens up the possibility that there is something similar available (but unknown) that would work with the recursive prime function as well. Even more interesting is that this indirectly states that there is more to our axiomatic abstractions, then just the axioms themselves. In a way, they sit on a "consistent" and "logical" foundation, which itself has an intrinsic about of information, which indirectly controls the representations of the axioms and allows (or does not allow) for alternative isomorphisms.

We can see this as the number system itself (as a formal system) allowing for the mapping between Binet's formula and the Fibonacci sequence.

Getting jiggy with it, if we extrapolate this out a bit farther, we can draw a conclusion that there are likely an infinite number of alternative isomorphic representations, any of which can be built on some intrinsic information contained by the rather large space of an infinite number of possible formal systems.

That opens the door to easily saying that just because we have not found an obvious alternative representation of some mathematical object, doesn't in any way imply that there are not some other "useful" ones (there are an infinite number of non-useful ones :-). Or in short, for those that are interested in it, I wouldn't write off the possibility that P=NP just yet, no matter how counter-intuitive the problem appears.


PRIME SUMMATION CHART

The Prime Product Chart proved so useful, that I started searching for a similar type of representation for addition and subtraction.

Realistically, the Prime Summation Chart should have a similar structure to the Product one, but be focused on addition. The Product chart broke down the factors, essentially dealing with the sub-structure of the numbers. In a related fashion the summation chart will break down the base numbers based on partitioning them into prime terms.

It is believed that all numbers can be decomposed into either the sum of two or three prime numbers. With that in mind, if we are looking for arithmetic partitions, we should concentrate those that only involved prime numbers and those that involve a minimum number of them.

The Prime Summation Chart should be similar to it's multiplicative cousin, so once again it's the numbers going down and the lowest prime (in the partition) on the right.

Now with addition since there were so many different partitions I had to narrow it down somewhat to the more interesting ones. This version of the chart sits on the middle numbers for the next round.

I went that way initially because I suspected that partitions involving 1 were going to be trivial, and thus not interesting.

This is similar in many ways to the product version, except that it is using summation.

Wherever possible I tried to represent the numbers with the absolute minimum number of primes, but always primes, since they are the main building blocks.

Although, for each new row there were many different possibly partitions,  in the list of possible partitions I high-lighted the outside elements in orange, and the inside one in grey

Interestingly enough, in the chart is how the patterns of primes keep repeating downwards and to the left. This attribute actually makes the chart fairly easy to generate and verify.

Still, while this chart shows some interesting patterns, it is still fairly complex.

If choosing the center of the possible partitions produced something complex, it might be interesting to see what the trivial choice for partition produces:

I dropped most of the triple partitions, and always picked the most trivial partition for the next row (which I high-lighted in grey).

It is really interesting to see how the patterns of descending numbers are reproducing themselves again and again in each column. The nth prime column just starts the pattern all over again for each row. Generating entries in this table is actually a simple, manual process.

Initially most numbers are either a prime or a product of two primes. But 27 and 35 both don't have any two prime number representations.

The question, is whether or not there is always at least a three prime representation or if at higher numbers it will degrade to four, five, etc.

The answer to this lies in the fact that each new column repeats the same pattern over and over again. It is this property that controls how the higher numbers get generated.

The most obvious point is that 27 and 35 only become partitions of three because the gap between primes is greater than 4. That is, the next numbers are always going to be X plus the last prime. So it's P, then 1 + P, 2 + P, 3+ P, etc. Except that there is not single one-prime representation for 4, so it must become (1 + 3) + P.

Any time the gap between primes is equal to 4, that number can only be decomposed into three prime numbers, not 2.

So, extrapolating a bit, what happens when the gap between numbers reaches 27? If 4 was the first non-prime number that needs to be represented as 2 prime numbers, then 27 is the first prime number that needs to be represented as 3. Thus the smallest partition is going to be:

1 + 3 + 23 + Pk

Where k is some value such that Pk - Pk-1 >= 27.

From this we can guess that this particular circumstance will continue infinitely. Each new entry that can't be represented with some limited number of primes will force some new entry into the number system. So for any N, there is always some number that cannot be represented with less than N prime numbers (thus showing that some of the original guesses over the years were probably wrong).

What might be interesting is whether or not these numbers fall on even or odd numbers. It wouldn't surprise me to see them flip flopping between evens and odds, or just staying with the odd numbers themselves (there is an existing proof in this area which may or may not conflict with the above).

UPDATE:  The range between the primes 2971 and  2999 may be the first one greater than equal to 27. The number 2998 can be expressed as: 1 + 3 + 23 + 2971, but is there also some prime decomposition that is smaller (with only 2 prime terms?)? If so, then the Goldbach conjecture stands, if not then it is wrong. It's easy enough to brute force my way through this search, so hopefully in a few days I'll try, and then update the blog again.My guess is that there won't be another smaller decomposition into primes AND the number 1 + 3 + 23 + 2971 + Pk, where Pk - Pk-1 >=2998 will be an odd number. Thus implying that the minimal decomposition (into 2 or 3 primes) is neither true for odd nor even numbers.

UPDATE2:  Interestingly enough: 2998 = 2 * 1499 = 1499 + 1499. And the smallest decomposition is 2998 = 29 + 2969. Also the smallest composite that is 27 numbers away from a prime is 1354. Oddly, like 2998 the following relation also occurs: 1354 = 2 * 677 = 677 + 677.

The first gap of 35 occurs between 9551 and 9587. Also, 9586 = 47 + 9539 = 2 * 4793 = 4793 + 4793, which shows that it has the same underlying decompositions as the case with 27 (which is exactly as we would expect).

So all of these numbers have the property that Ck = 2* Pi = Pi + Pi. In that way, even if 27 and 35 can only be the sum of three primes, their pattern multiples (1354 and 9551) are back to being expressible with 2 primes. Which (loosely speaking) means that the conjecture is true (although I'd like to state it as every number can be minimally stated as the sum of 1, 2 or 3 primes).

UPDATE3: While I'm here: there are no two-prime decompositions of 27 and 35, because both numbers are odd, and except for 2, all primes are odd numbers. To be decomposable into two primes Pa and Pb, the following must hold true:

Pa = 27 - Pb   (or 35)

And since Pa can't be even (divisible by 2) Pb must be even (and thus not a prime).

(the concept of 'odd' numbers is clearly useful beyond things just being a factor of 2, so is it possible to extrapolate that to higher numbers, say 3, for instance? Could be call that "trodd" ? Or is it just Friday?)

UPDATE4: This is my last update, I promise. I just started thinking that every positive natural number (k) can be deterministically generated (in sequence) from the following rules:

• The number is a prime number Pi
  
• The number is an Nth entry away from a prime number, either as the last prime plus another, or the last prime plus two others. So Pi + Pa or Pi + Pb + Pc
  
• The number divided by two is a prime number, so Pi + Pi
  

Then a stack-based algorithm to generate all of minimal prime sums for all of the numbers is:

1. Check if the number is prime, if so use that number and reset the stack
   
2. If not, take the last prime and the last numbers on the stack
3. If the last numbers are one or two, use them plus the last prime
4. Else divide the number by two, and use it twice
5. Finally: add the representation (numbers) to the stack
   

The only question left over, is we know this appears to work for expansions of 1 + 3, but does it work similarly for the next two-sum expansion 1 + 5 ? The first gap where that shows up is between 89 and 97, where 95 = 89 + 1 + 5, and there are no smaller representations. If everything holds true, then

95 + Pk = 2 * Pi

where both Pk and Pi are primes, and there are no prime numbers in the range (Pk, Pk+95]. One quick check shows that this doesn't occur in less than numbers less than 25,000. Maybe I'll need another update after all :-)


SUDOKU

Getting way back to generating large prime numbers, I suspect that it is entirely possible to work backwards from some point in the number space to finding any nearby associated prime numbers.

Although primes clearly have a pattern, to get to the Nth element in the pattern, one has to take in account all of the "information" from the previous N-1 elements.

For massive numbers, this is a huge amount of information. However I keep thinking it might be similar to solving a Sudoku puzzle.

In a Sudoku puzzle, there is a relationship that each number only appears uniquely per row, per column and per square (the major ones).

The puzzle starts with a few numbers filled in (which we can see as information). In order to solve the puzzle, readers can utilize all of the intrinsic relationships in order to absolutely assert the location of a specific number. It's not a puzzle where one needs to guess, you can "absolutely" be certain that a number appears in a specific location if and only if you have made the correct inferences from all of the available information.

As such, it is deterministic, and once someone starts the puzzle (assuming that it really is a valid Sudoku puzzle), it can always be correctly finished. No guessing, no wrong answers, no ambiguity.

Within the number system there are a larger number of 'partial information' holders that can be used to say something relative about a range of numbers. We know all sorts of relations that occur between numbers that do not need to be tied to all of the intrinsic structural knowledge.

That is, we could drop into a range of numbers and starting at one specific point, make associations between the various different sets of numbers. We can make some high level associations, but also some low-level ones, such as that some number is a power of 2.

If we can build up enough information, over a large enough range, we should be able to correctly infer that some of those numbers in this (increasing) range are prime numbers.

This is very similar to how I produced the Prime Product Chart for the block-start number 30031. I didn't have to compute everything up to that number in order to be able to diagram the number itself. I just started by placing 30031 in the center and worked my way outwards on both sides. Each time I factored the nearby numbers, I updated the chart to show there revised structure.

Of course for that example, I cheated somewhat. I had access to a UNIX factor program, which quickly and conveniently produced the correct factors, that I added to the graph.

Still, if factor can be seen as producing an "absolute" reference to some information (factors in this case), I suspect that there is a "relative" variant that could still provide reasonable information that we can use.

Even small operations are expensive on multi-million digit numbers, so to be practical we'd have to produce some pretty strong information based on very little related information. With enough of it, we could re-construct the surrounding numerical space, and then draw inferences about the elements in that space.


FINAL NOTES

There is more. Lots more. I manged to get the major points out for each of my key focuses, but it'll probably take me a long time to sift through the details and find all of the rest of things of interest.

My biggest problem is being able to find the time to explore this world of primes to the degree that my curiosity is calling for. It's nice because it is simple and accessible, but often I find I have to think about things for a long time, or spend a lot of time reading books on topics like Number Theory.

Hopefully in the new year I'll get a chance to do some follow up work. I'd really like to try experimenting around with finding inexpensive "relative" relationships. Some intuitive inner-voice suggests that that might be very workable. Or perhaps, I might just wait again, until the next weird dream wakes me up in the middle of the night. I managed to get a fair amount of traction from that last one.