Why doesn't (1,2,6)(6,3,1) work as a solution for r=2?

Note that if you allow y to be prime, you can extend the argument above to any gap. Put another way, for any prime (and also for any composite) y there is an x such that conjecture 1 fails for that x and y, and x will often differ from y by at most a constant times log y .

It might be useful to consider structures where FTA and analogues don't hold. I think that gives a more accurate picture than might be present from a RM equivalence in a theory which may not be as weak as you want to see things clearly.

While mathematically distinct from your problem, you can get a feel for the probability through an example like this: Given n randomly chosen vectors in {0,...,k}^n viewed as a cubic lattice, what is the likely hood that all n land on a face of the cube (the jth component has all 0 or all k for the n vectors)?

Oh Johannes, how delightfully ambiguous you are!

Notice equality occurs if A=I. Can you rewrite (A+B) as A(I + A^(-1)B) and find appropriate square roots of A^-1 B ?

While representation in machine language is important, especially from an algorithmic perspective, I'm afraid the statement regarding rationals contradicts work on Hilbert's tenth problem. And further work (undecidability of Robinson's arithmetic) also suggest no decision procedure for such systems over the rationals.

Also, I think James Cranch misspoke: for the reals (not rationals) and certain algebraic systems, there is a decision procedure. The link James provided gives some detail.

See Tarski's work on the decidability of (real closed?) fields. You need to be more specific about the system. For example, it might be undecidable if a cosine term is there (in which case Tarski's work does not apply).

In the interest of clarity, can you tell us what w is and what w and the a's have to do with L_f(w) ? Also, I am guessing that f(n) > n is an f that plays no role in this problem. Or can it?

This sounds like a graph reconstruction problem. What will you do with such a deck (set or multiset) of partitions?

As a search term, you could try "Landau's function" .

Ben's suggestion gives a good starting approximation. You will need to use prime powers at some point; the answer I give tells you what to look for for a more precise answer.

Unfortunately, I know a real efficient constant time such algorithm. The problem is to find one that does something adequately useful. It is also unclear how far "adequate" can be realized.

If n were rational, it might be possible to prove that the difference between the roots is also rational.

There is an exercise attributed to Burris and Kwatinetz at the end of Chapter 1 in the book "Algebras, Lattices, Varieties Volume I" which mentions (for countable algebras of countable type) similar results on the size of the automorphism group and endomorphism monoid and congruence lattice as well.

Have you checked the Handbook of Combinatorial Designs? They might give as complete a catalog as you are likely to find off the web. Also, it is likely (but I do not know) that the number is super exponential in the order of the matrix, so it is not clear to me what you would do with a catalog.