It is not clear what the source algebra is. What relations/equations do n-ary semigroups satisfy? What arity does f have? Do you want the inclusion i and the existence of a term t of * of the appropriate arity such that i(f(stuff_from_A...)) = t(i(stuff_from_A)...)? Your F_n(A) does not seem to be closed under the operation as I understand it. Gerhard "It Must Be Something Else" Paseman, 2015.09.22

Stevens used (what I call) Bonferroni inequalities to truncate the sum. Brun did this earlier and with more refinement to get better results. How practical depends on what you want. I made small refinements to Stevens's work to get an improved explicit but unoriginal upper bound on Jacobsthal's function (ArXiv 1311.5944, if you're interested). I think you should try it and see if it works for you. Gerhard "Got Some Satisfaction From It" Paseman, 2015.09.18

See mathoverflow.net/questions/88777 . Gerhard "Likely To Close As Duplicate" Paseman, 2015.09.18

Quite possible, in which case my reference won't help. However, more general notions of commutation (including the one you are using) have been studied in the context of general algebra. I am not willing at present to answer general questions, but if you think something I've suggested might help and have a specific point to resolve, I can probably help. Good Luck. Gerhard "Longest Commute Was Four States" Paseman, 2015.09.17

If you need to come at this from a functional analysis point, I can't help. If you don't mind a general algebraic approach, there is a notion of commutator for general algebras. Freese, Kiss, and McKenzie are some authors that come to mind. If you come back with a question related to this question and concerning a point in commutator theory, I might be able to provide a hint. Gerhard "Then Again, I Might Not" Paseman, 2015.09.17

I find the conflict in notation unfortunate. If instead you just used $\zeta$, and reminded people that $\zeta = -1 \bmod (1 + \zeta)$, I would find your presentation much easier to read. Gerhard "Also Needs Fewer Greek Letters" Paseman, 2015.09.17

Welcome to MathOverflow! As you may be able to tell, you have a well-written first-time question here that is appreciated by the community. I wish you success in your studies, and look forward to more quality questions from you. Gerhard "Also Try Answers And Comments" Paseman, 2015.09.17

Note that for k > 25 the terms seem to be smaller than (100 choose 25)*(2^{-99}), which should be small enough for the desired precision. So only 300,000 terms need be computed. Further, for fixed r, the sum is alternating , so pick k which yields the desired tolerance, perhaps k=20. Gerhard "Why Add Zero To Zero?" Paseman, 2015.09.12

The lower bound of Westzynthius involves sifting an interval $[R, R+ p_n\xi]$ with the first n primes in three stages: cross out multiples of all of the (k+1)st through lth primes, then choose residues to maximally sieve the remaining with the first k primes. This leaves much fewer than n-l holes in the interval to be covered by the remaining primes. $\xi$ in the paper is "like" a constant times $\frac{\log \log p_n}{\log \log \log p_n}$. I intend to post a review of the lower bound argument eventually. Gerhard "Still Playing With Upper Bound" Paseman, 2015.09.11

The bound is reminiscent of Westzynthius (1931). A reference for this work can be found at mathoverflow.net/questions/37679 . Gerhard "And A Few Other Places" Paseman, 2015.09.10

Also, sometimes it helps marginally to fudge on m: if you can pick m to be one less but have 1 - sum > 1/2p_m, that will also work. In any case for large m (m > 3) we can have both m^e < n and \phi(M)4 log m > M while keeping (1 - sum) comfortably large. Gerhard "And Always Weaken The Inequality" Paseman, 2015.09.10

This is posted primarily in response to the last conjectured inequality in the question, which for large n is true, but limits d to (for large n) some value greater than n/4. It is quite possible that d can actually be as small as 2, but no one has seen a proof for all n> 2. More generally, given an integer N with two distinct largest prime factors p and q, I know nothing contradicting the conjecture that two totatives to N exist in an interval of length pq. Gerhard "You Saw It Here First" Paseman, 2015.09.10

For finite sets of patterns, you might find some uniformity by assuming they are all kxk patterns for a signifcantly large k, and find out which "infinite strings" are allowed by (say left-right) concatenation. Then find out which strings are compatible by placing certain strings on top or on bottom of other strings. You might be able to show that a periodic density-maximal solution exists with this approach. Gerhard "Is This Related To MineCraft?" Paseman, 2015.09.10

Thank you for your confidence. My major problem is understanding $\alpha_{p,k}$. In spite of the word interval, it is unclear if this represents a set or an interval of consecutive integers, and I don't know why the subscripts of the set members. You also use $\alpha_q$ with a single subscript which may suggest a single such interval or a multiple: it isn't clear. Also, I don't buy the reason why your unnnamed inequality (ending in $1/p_n$) does not give you the desired belief. The belief is wrong because reality differs. Gerhard "Never Bets Against Reality. Period." Paseman, 2015.09.09.

In particular, if G has a vertex v with distance greater than r to all other vertices, then v can't belong to any of the k subsets. Are you promising anything with respect to r, or is an additional goal to find a minimal such r? Gerhard "The Problem Behind The Problem?" Paseman, 2015.09.09

You are going to need r big enough so that such a decomposition is remotely possible. I'm thinking that the subgraph T_r of G which contains only edges of length less than r has to be k-connected or something along those lines. Are there quick ways to determine if T_r "might be connected enough"? Gerhard "Maybe A Simpler Hard Problem" Paseman, 2015.09.09