Sorry. I am having problems following the reasoning in the question: I am not that facile with probability in the context of prime (or of totative) distribution. Gerhard "Am Working On My Aims" Paseman, 2015.09.09

Actually, Lehmer has a slightly more restricted version in which he shows (regardless of a), that the difference in counts between two such intervals is 2^(k-1). For more on this, see mathoverflow.net/questions/88777 . I am having problems following your reasoning; the best I can do is infer what results might occur from the literature that I know. Gerhard "Helps Knowing Truth In Advance" Paseman, 2015.09.09

In particular, make sure a is large enough to include 2^k totatives in one interval, and then all the other such spaced intervals will have at least one totative. However (see my Westzynthius question) there are sharper bounds for an even larger collection of intervals (smaller in length than k^(4(1+ log log k)) even) . Gerhard "Wrote An Article About It" Paseman, 2015.09.08

See Lehmer's 1955 paper On distribution of totatives. Under certain conditions on a relative to n, there is an equal distribution among the a intervals. Even without this, it is known the variance is below 2^k, where k is the number of distinct prime factors of n. This should help with some of your questions. Gerhard "Also Relates To Cyclotomic Polynomials" Paseman, 2015.09.08

These comments of yours (and the question) are better suited for math.stackexchange.com. It has been decades since I looked at an undergraduate text in logic. I used Enderton in a previous millenium, and I understand some other books have come out since then. You might do a web search on books that contain the phrase "positive existential" in books with the title including "logic" or "metamathematics" to find something newer. Also, there are web resources available. Gerhard "Why Choose This Particular Paper?" Paseman, 2015.09.07

The issue is a little more complicated: we don't know if * (multiplication) can be defined from the given theory. However, even without that, if the theory containing just the degree one polynomials is not decidable, there is not hope for the full existential theory to be decidable either. I recommend reposting this with links on math.stackexchange and reviewing what terms and what formulas are for this theory. Let them know what your background is, so that a good answer can be given. Gerhard "Practice On Some Other Theories" Paseman, 2015.09.06

There should be recent results that give some hope, namely that $\omega(n)=\omega(n+1)$ for infinitely many $n$. However it does not settle Joseph's question. Gerhard "Remembering Results For Other Functions" Paseman, 2015.09.05

To name, no. However, you can use Westzynthius's construction to build one. It will require lots of primes. Current calculations suggest you will need x > 50. Gerhard "Check Out Thomas Hagedorn's Paper" Paseman, 2015.09.05

I would interpret the original poster's request as: interpret the LHS as L(x), the RHS as R(x), and ask how far L(x)/R(x) strays from 1. Using your first displayed expression, asymptotically it seems the variance is like e^stuff/(log x)^2, where stuff is the negative of the exponent in your O_epsilon term. It would be interesting to find for which x L(x)/R(x) strays furthest. Gerhard "Likes Taking Things To Extremes" Paseman, 2015.09.03

@YaakovBaruch, I am surprised. I must have been thinking about something different from what I said. Thank you for the links. Gerhard "And It Wasn't Floor Either" Paseman, 2015.09.03

Which is as I suspected, a pattern of least prime factors of integers n with central number a multiple of a primorial. While some of the large prime gaps are near multiples of large primorials, many do not have such multiples near the center. I show my bias when I say it makes more sense to study the distribution of totatives to a primorial, and see where those large gaps appear. Gerhard "Sensing A Philosophical Clash Here" Paseman, 2015.09.03

I think you will find nonsymmetric patterns will abound with large values of x. You might consider looking at recent papers on large prime gaps. They are implicitly constructing denizens using a log's worth of small primes and interesting sprinklings of large primes, starting with a base of medium primes. I think the symmetric depth for these will be pretty small, and I don't even understand the definition of symmetric depth. Gerhard "Check Out Rankin And Pomerance" Paseman, 2015.09.03

If instead of 3x+1 you had ceil(\alpha x + 1) with \alpha smaller than 2, you could show convergence pretty easily. My feeling is that there is a threshold between 2 and 3 where for \alpha below the threshold, it will be easy to prove convergence, and for \alpha above it, it will be hard. Gerhard "The Threshold Might Be Two" Paseman, 2015.09.03

Based on mathoverflow.net/questions/216251/… , my guess is it is a binary relation (as p is fixed), and that this question will not have a concise and suitable answer. Gerhard "Unsure And Undecided About Suitability" Paseman, 2015.09.02

You need to understand what terms are and what formulas are for this language, and what axioms are present so that certain things which are not present in the language (like a symbol for the constant 1) can be definitionally equivalent. I think F(x,y,z) could be a term like (x+(y+(x+(z+x)))), which would be like a multivariable polynomial of degree 1. If you are having a challenge with this, you might try math.stackexchange.com. I could see undergraduates near the beginning of a logic course answering this. Gerhard "Unsure What Else To Say" Paseman, 2015.09.02

The F_i and G_i are likely functional terms in the language, and so may contain +. They are degree one multivariate polynomials most likely because they are easily expressed in this language. (There may be a term-equivalent definition of a multiplication relation that works for this structure, but I am not seeing it. Thus they are "adding" variables together, not "multiplying" them.) Gerhard "Try Building Some For Yourself" Paseman, 2015.09.02

Also, while there may be a relation between $\pi(x)$ and $\pi^{-1}(m)$, I never planned to use the two in the same article. Gerhard "Like Edward Teller And Anti-Teller" Paseman, 2015.09.02

Different context. I used sigma ^ -1 for the sum of reciprocals of distinct prime divisors, and pi ^ -1 for product of (1 - reciprocal). I was dealing with counting consecutive nontotatives (non coprimes), not primes. Gerhard "Seemed Natural At The Time" Paseman, 2015.09.02

It should be clear. M_n is flat with one maximal antichain of n elements (and ratio of n/n+2). The sublattice induced by taking the Boolean lattice of subsets of a (2k+1) element set and identifying all the subsets of size less than k, and then identifying all the subsets of size greater than k+1, is pretty flat, with all but two of its elements belonging to one of two disjoint maximal antichains, giving a measure of m/m+2 for m a quantity nearly exponential in k. You need to think about what flat "means" . Gerhard "Go And Play With It" Paseman, 2015.09.02