Michael Brand VAC29 1024 = (4-2)10 25=52 But not any power of 10. In other bases: B-Friedman numbers 11001TWO 101TWO 10TWO -- Erich Friedman (2000) F (n) x Friedman 0 x n lim F (n) / n ? n We prove =1 Not just for Friedman numbers, but also for B-Friedman numbers in any base B. Step 1: We show that there exist Friedman infixes. ◦ ∃(m,k), s.t. ∀a, b, L(b) k a.m.[ 0] .b Friedman t k Step 2: We show a systematic way of constructing Friedman infixes with many different k that all share a constant l=L(m) and all satisfy l|k. Step 3: We show that the number of possible k grows with l enough to conclude a density of 1. “Yields a falsehood when appended to its own quotation” yields a falsehood when appended to its own quotation. -- W.v.O. Quine quines (Bratley and Milo, 1972) 10411041 = 1041 × (104+1) LB ( s ) r B 1 r [ sB ] s LB ( s ) B 1 We need a method to unambiguously encode an entire tuple in a single number. ◦ We don’t need every single integer tuple to be representable, but we do need a sufficiently dense set. ◦ We do need to minimize the number of extraneous digits used. Solution: encode the tuples of radical-free integers. enc x1 , x2 ,, xn x1 xn x2 For any x and s>0 there is a number cx s.t. x can be represented by cx repetitions of s. For example: if x 0, ss s s x otherwise. s s x A Friedman infix: m = [s]r = [s]r’s, for any s>3 and any large enough r’, with a suitable k = k’L(s)r = k’L(m). L(s)r 10 1 r t L(s)r 10 k 'L ( s ) r 0 a.[s ] .[ 0] .b a (0 10) s L(s) 0 b 10 1 t times k (0,10,L(s),s,10L(s),1,10L(s)-1,10,L(s)) all, together, in the span of some constant, C, repetitions of s. r ∈ span([s]r’) by s+...+s. We need 3 of them. This leaves k’ ∈ span([s]r-(C+3r’)) = span([s]r’(s-3)-C). m = [s]r’s. k’ ∈ span([s]r’(s-3)-C). We want to choose a good s. Chooses to be the concatenation of radicalfree integers. Let G be the number of unique order arrangements for these integers. |span([s]r’(s-3)-C)|≥Gr’(s-3)-C. By using the infix m=[s]r’s, we constrain only L(m) =r’sL(s) digits. By choosing k=k’L(m), we ensure the constraints are independent for different k. The density is therefore bounded from below r '( s 3 )C G by r ' sL ( s ) 1 1 10 A density of 1 follows if Gs-3>10sL(s), because we can take an arbitrarily large r’. In base 10: ◦ taking s to be the concatenation of all radical-free integers of up to h=3 digits, repeated d=13 times. For a general base B, we need to pick h=h(B) and d=d(B). Using a large enough d, one can use Stirling’s formula to reduce G>BL(s)s/(s-3) to log B k i 1 iki / k h ◦ Shorter than minimum message length! For a large enough h, the radical-free integers’ expectation converges to that of all integers in the same range, which satisfies the property. □ questions?