Erik Westzynthius was a Finnish actuary whose major contribution to mathematics was a 1931 paper on a sieving process. This process showed that for any constant C, there were infinitely many primes p_n such that p_{n+1} > p_n + Clog p_n. Before then, no one knew prime gaps could get much larger than average. Gerhard "Terry Tao's Blog Has More" Paseman, 2015.03.17

If the two functions range over disjoint domains, you probably can do binary search as needed. If the functions share a domain, you have interactions which may take more than polynomial time to resolve. It may be possible to divide the domain into finitely many regions and solve the problem quickly in each region, but it is not clear that you will have only polynomially many such regions. Gerhard "Hopefully They Are Convex Enough" Paseman, 2015.03.17

They had better have different speeds. My experience otherwise is that the balls hit each other and miss the bins entirely. Gerhard "Hopefully Simultaneity Is No Issue" Paseman, 2015.03.17

It may develop that you are after zero-density subsets of the primes, where there is some already developed notion of density. You might search this forum for the word density with some number theory tag attached. Gerhard "The Answer May Be Close" Paseman, 2015.03.17

Note that the set is related to the totatives of finite products of members outside of S. In particular, if the complement of S is a finite set T, the product of the members of T is then called n, then S is related to the totatives of n, and your epsilon can be chosen not much smaller than a constant times 1/log(log(n)). The next thing to look at would be S having only those primes congruent to b mod d for some integers b coprime to d. Gerhard "Ask Me About Erik Westzynthius" Paseman, 2015.03.17

Following up on Ricky Demer's suggestion, it seems natural to me to replace the current system with a slightly more complicated one: for n=6, have a six-square ring replaced by a number in [0,63], with 144 combinations possible for entry and exit points, of which only 48 are used. Although this only halves the number of steps, using this representation may allow some number theoretical analysis to show how quickly certain configurations are reached. Gerhard "Also Has Small Transition Table" Paseman, 2015.03.13

I should think so. Not an argument, but the following might become one. Suppose one tries to select m colors from a colored graph, say by choosing the m most popular colors. If it fails, the complement contains a connected and complete bipartite graph, which presumably has many more edges because n is so large. This should at least give bounds on n. Gerhard "Can't Count: Not Enough Coffee" Paseman, 2015.03.05

Etiquette (and good practice in general) is to have such edits accompanied by a brief acknowledgment, e.g. "thanks to kjetil b halvorsen..." or "I learned from kjetil b halvorsen that...", even if the insight is not original with the person who helped inspire it. Gerhard "Plenty Of Space For Acknowledgment" Paseman, 2015.03.05

I've just realized that the above counts nonzero such functions; the representation ignores the identically zero boolean function $(x_1 \wedge \neg x_1)$. Of course, this only adds 1 to the count, but care should be taken by the reader to see that no other details or functions are missing from the analysis. Gerhard "And Thanks For The Upvote" Paseman, 2015.03.02

Of course, there is also an obvious lower bound of $2^{4j}$, where $j$ is floor of $n/2$. However, this class may yield to an exact enumeration, if not a closed form for $C_n$. Gerhard "Good Lower Bounds Often Hard" Paseman, 2015.02.27

I've received an indication to clarify. When looking at a problem, several perspectives are often useful. The notion of residual finiteness allows one to shift between or adopt several perspectives. This is one aspect of "picture in picture" (a feature on some TV monitors). Another is that this answer attempts to surround the questioner's "big picture" for group theory with an "even bigger picture" of general algebra. I find the signature useful in suggesting a point germane to and indirectly addressing the question. Gerhard "Signatures Are Important To Me" Paseman, 2015.02.26

Good! Are the known bounds on the number of partial orders easy to demonstrate? Gerhard "Likes Things Easy To Order" Paseman, 2015.02.26