User halfdan faber - MathOverflow

Status of Beal, Granville, Tijdeman-Zagier Conjecture

2010-06-19T17:06:37Z

The Beal, Granville, Tijdeman-Zagier Conjecture, i.e.

If $A^x+B^y=C^z$ , where $A, B, C, x, y,z$ are positive integers and $x, y$ and $z$ are all greater than $2$, then $A, B$ and $C$ must have a common prime factor.

... and it's associated $100K prize for proof or disproof seems to have gone largely unnoticed in the mathematics community. Please answer with (A) references to past or ongoing research or (B) references to equivalent forms of this conjecture known prior to Andrew Beal posing it in 1993.

Major mathematical advances past age fifty

2010-05-23T06:56:26Z

From A Mathematician’s Apology, G. H. Hardy, 1940: "I had better say something here about this question of age, since it is particularly important for mathematicians. No mathematician should ever allow himself to forget that mathematics, more than any other art or science, is a young man's game. ... I do not know an instance of a major mathematical advance initiated by a man past fifty. If a man of mature age loses interest in and abandons mathematics, the loss is not likely to be very serious either for mathematics or for himself."

Have matters improved for the elderly mathematician? Please answer with major discoveries made by mathematicians past 50.

Answer by Halfdan Faber for number of zeroes in 100 factorial.

2012-07-20T18:30:50Z

Using well known approximations for the length and number of trailing zeroes of n!, and making the reasonable assumption that the inside zeros appear with frequency $\frac{1}{10}$, we get the following approximation of the total number of zeros, t, in n!:

$t = \lfloor \frac{1}{10}(\frac{\log (2 \Pi n)}{2}+n\log (\frac{n}{e})- \frac{n}{4}+ \log(n)) + \frac{n}{4} - log(n)\rfloor $

Which simplifies to:

$t = \lfloor \frac{n (9 \ln (10)-4)+4 (n-9) \ln (n)+2 \ln(2 \Pi n)}{40 \ln(10)} \rfloor$

This approximation seems to work well for n up to at least 10,000.

100!, with digit length 158, has less inside zeroes, 6, with 24 trailing, than the normal expectation for a total of 30, with t=36.

98! is "zero-perfect", i.e. inside zeroes appear with exactly frequency $1/10$, with actual total zero count 35 and $t = 35$

Other examples of zero-perfect factorials are: 1009!, 1097!, 1112!, 2993!, 6128!, ....

There appears to be a strong correlation of n having only 0-3 prime factors in {2, 3, 5} if n! is zero-perfect. Uneven n is often a prime number if n! is zero-perfect.

Answer by Halfdan Faber for {transcendental numbers} \ {computable transcendental numbers}

2010-05-30T01:47:03Z

Note: Answer is pending update per attached comments.

The difference, stated informally, is that that the non-computable transcendentals in their k-base digit representation are entirely random and non compressible. A computable transcendental, such as e, can be represented by a finite algorithmic description, such as a series expansion, which is a form of compression. For the non-computable numbers no such shorter representation exist. Their shortest computational description is their own infinite digit sequence. You can read more about computational complexity here: http://en.wikipedia.org/wiki/Kolmogorov_complexity.

There is a wealth of similar numbers to the Ω class of numbers. In general it is "easy" to come up with new definitions for such numbers. These all belong to the countably infinite set of non-computable definable numbers.

To make matters worse, what is left are the non-definable (and therefore also non-computable) numbers. They are the numbers that cannot be described in any way what-so-ever, other than by just iterating through their infinite non-compressible digit sequence. The set of all non-definable numbers is uncountable.

Cardinality of the set of all paths in the infinite complete infinitary tree

2010-05-23T04:36:28Z

The cardinality of the set of all root paths in the infinite complete binary tree is equal to the cardinality of the Continuum. The same holds true for k-ary trees for any finite k. But what is the case for k infinite?

Answer by Halfdan Faber for Textbook recommendations for undergraduate proof-writing class

2011-04-25T02:38:00Z

In addition to those mentioned, here is a good book which is just under $30:

http://www.amazon.com/How-Think-Like-Mathematician-Undergraduate/dp/052171978X/ref=pd_sim_b_5

What is the longest known sequence of consecutive zeros in Pi?

2011-04-24T22:23:23Z

Inspired by this question, I would like to know what is the longest known sequence of consecutive zeros in Pi (in base 10).

So far the longest I have found is the sequence of 8 zero's occurring in position 172,330,850 after the decimal point.

If we expand the question to longest sequence of identical digits, 6 takes a lead with 9 digits occurring at position 45,681,781. All other digits have 8 digit maximum sequences occurring within the first 200,000,000 digits.

In general what is known about the distribution of k-length b-sequences in Pi, where b is any of the base digits? Can something be learned about the normalcy of Pi from these distributions? NB, by distribution I mean the set of (k,b,f) triples, for a given base, where f is the first position of occurrence.

Infinite graphs as functional operators

2010-09-29T07:37:42Z

Original Question

Consider an infinite tree of constant degree $k$. For such a tree we can consider the total number of nodes at depth $n$, $g(f)$, and the total number of paths from the root, $p(f)$, to be a function of the constant function, $f=k$. We define $G(f)$ to be the resulting infinite tree. Now let us generalize this idea to functions $f(n)$, with the normal convention that the root has depth $n=0$.

Some examples:

$g(1)=1$
$p(1)=n+1$
$G(1)$ is the infinite tree (path) of constant degree 1

$g(2) = 2^n$
$p(2) = 2^{n+1}-1$
$G(2)$ is the infinite complete binary tree

$g(a) = a^n$
$p(a) = \frac{a^{n+1}-1}{(a-1)}$ for a>1
$G(a)$ is the infinite complete tree of constant degree a

$g(f=n) = n!$
$p(f=n) = !n$
$G(f=n)$ is the infinite complete tree of incremental degree

$g(f=n+1)=(n+1)!$

$g(f=2n)=2n!!$
where !! is the double-factorial

$g(f=3n)=3n!!!$
where !!! is the triple-factorial

$g(f=n^2) = n!^2$

$g(f=n^a) = n!^a$

$g(f=an^b) = a^{n}n!^b$ ; Sequences not in Sloan for a>1

$g(f=n^2+n+1)$ = ? ; Related to absolute values for Sloan A130031
$p(f=n^2+n+1)$ = ? ; Sequence: [1, 2, 7, 62, 1107, 31412, 1273917, ... ]

$g(f=2^n)=2^{((n+1)^2-(n+1))/2}$

$p(f=2^n)= ?$ ; Sequence: [1,3,11,75,1099,33867, .... ]

$g(f=a^n)=a^{((n+1)^2-(n+1))/2}$

$g (f=n!)$ = Sloan A000178

$g (f=2n!)$ = ? ; Related to Sloan A156926. Sequence: [1,2,8,96,4608,1105920,....]
$p (f=2n!)$ = ? ; Sequence: [1,3,11,107,4715,....]

$g (f=3n!)$ = ? ; Sequence: [1,3,18,324,23328,8398080,....]
$p (f=3n!)$ = ? ; Sequence: [1,4,22,346, 23674, 8421754,....]

$g(f=a^{a^n})= a^{a^{n+1}-a(3^n + 1)/2}$

My questions are: is this graph construction well known? I would be interested in any references to similar functional transformations on graphs.

Also, could anyone tell me what is the cardinality of the set of all paths in G(f=n)? Clearly it has at least Continuum cardinality. Since the factorial grows faster than $a^n$, yet slower than $2^{2^n}$, I would think it lands in the Continuum. I am not sure, though...

Addendum

We can express p and g as functional equations:

$g(f(n))=f(n) g(f(n-1))$

$g(f(0))=1$

$p(f(n))=\sum_{i=1}^{n} g(f(i))$

If we extend to the complex domain and consider the special case f(z)=z we have the functional equation:

$g(z)= z g(z-1)$

Which has the rather well known solution $g(z) = \Gamma (z+1)$

Path cardinality for random $(a+b)$-ary infinite trees

2010-09-27T05:56:17Z

Consider a random infinite binary tree $T(a,b)$, so that $a$ denotes the probability of a left edge branching from any root-connected node,and $b$ denotes the probability of a right edge branching from any root-connected node. We establish an inductive base case, so that $T(0,0)$ contains the root node only.

$T(1,0)$ and $T(0,1)$ trivially has path cardinality $\aleph_0$ (*) . $T(1,1)$, the infinite complete binary tree, trivially has Continuum path cardinality.

$T(a,b)$ is finite for $a+b<1$.

$T(a,b)$ has path cardinality $\aleph_0$ for any $a+b=1$.

Now, is it then true that, $T(a,b)$ has Continuum path cardinality for $a+b>1$?

Intuitively this seems to be the case; Consider for example $T(1,\epsilon )$, for an infinitesimal probability $\epsilon$. On average for every $1/ \epsilon$ left-most nodes there is a right-branch. For each occurrence of a right branching node, we contract the graph, deleting all intermittent nodes which produced no right branch, constructing a new graph node, which branches both left and right. By induction we can then show that $T(1,\epsilon)$ is isomorphic to $T(1,1)$, and therefore has Continuum path cardinality. It seems a similar argument can be used for any $T(a,b)$ with $a+b>1$. Apologies if this is trivial. Does anyone know of any relevant references on path cardinality for random sub-graphs of the infinite complete binary tree?

(*) path cardinality of $T$ is short for the cardinality of the set of all paths in $T$.

Axiom of Computable Choice versus Axiom of Choice

2010-05-23T13:47:27Z

What would be the consequence of requiring that any choice function be computable; i.e. using as the foundational basis ZF + ACC? Does it make a difference if we admit definable functions?

I guess I am sometimes bothered by the thought that any random choice over an uncountable set by definition would seem to almost certainly return a non-computable member. This seems impractical and perhaps even problematic, considering that major branches of mathematics such as for example analysis, with only few notable exceptions, mainly operate within the computable or definable realm.

Presumably an immediate consequence would be that the Banach–Tarski paradox and similar theorems related to unmeasurable sets would fail. But would there be more fundamental consequences?

Answer by Halfdan Faber for Does the Axiom of Choice (or any other "optional" set theory axiom) have real-world consequences?

2010-06-23T05:34:57Z

Answering your question specifically concerning real-world consequence of AC, it is worth noting that the answer is strongly dependent on whether or not the universe is discrete or continuous. Although quantum mechanics and high energy physics hint at a fully discrete universe, this is not at all settled. For example it is not known whether or not space-time is discrete. If the universe is discrete, and therefore either finitely or infinitely countable, depending on whether or not the size of the universe is finite (also not known), the full AC is no longer applicable (a choice function for finite sets can be proven within ZF). In this case AC would seem exceedingly unlikely to have real-world consequences.

Responses from mathematicians concerning Flash trading

2010-06-05T15:02:37Z

Have there been any responses from the mathematics community regarding flash trading, for example from a game theory or system dynamics point of view? Please answer with personal comments or references.

According to Wikipedia: "Flash trading is a controversial practice of some financial exchanges whereby certain customers are allowed to see incoming orders to buy or sell securities very slightly earlier than the general market participants, typically 30 milliseconds, in exchange for a fee. With this very slight advance notice of market conditions, traders with access to extremely powerful computers can conduct rapid statistical analysis of the changing market state and carry out high-frequency trading ahead of the public market.[1]

Critics of the practice contend this creates a two-tiered market in which a certain class of traders can unfairly exploit others, akin to front running.[2] Exchanges claim that the procedure benefits all traders by creating more market liquidity and the opportunity for price improvement."

http://en.wikipedia.org/wiki/Flash_trading

http://www.nytimes.com/2009/07/24/business/24trading.html

Answer by Halfdan Faber for a^b = b^a when a is not equal to b.

2010-06-01T04:55:31Z

This is not an answer, but the solution to $x^{x+1}=(x+1)^{x}$ is known as the first Foias Constant.

For more information see: http://mathworld.wolfram.com/FoiasConstant.html

What is cardinality of the set of true undecidable minimal sentences in a formal theory of aritmetic

2010-05-29T22:31:27Z

Let T be a true theory of arithmetic to which the incompleteness theorems apply. Consider two sentences in the language of T to be equivalent if they are provably equivalent over T. How many equivalence classes are there, under this relation, that contain a true-but-unprovable sentence?

Hausdorff dimension vs. cardinality

2009-11-22T19:20:41Z

What is the relationship between the Hausdorff dimension and cardinality of a set?

Specifically, assuming the Continuum Hypothesis, if a set has Hausdorff dimension greater than zero does, that imply that its cardinality is equal too or greater than that of 2^Aleph_0?

Or, does the negation of CH, imply the existence of a set with positive Hausdorff dimension and cardinality strictly between Aleph_0 and 2^Aleph_0?

Answer by Halfdan Faber for What's so special about transcendental numbers?

2009-11-02T05:31:05Z

Adding to the above, it is worth noting that the transcendental numbers that are commonly known/used in mathematics (e, pi, etc.) belong to the countable subset of transcendental numbers with a finite recursive function generator. The uncountable transcendental numbers, or the random numbers, are those which cannot be generated by a finite recursive function, and they can therefore also not be the solution to a finite analytic equation (unless it contains random numbers or is solved by a subset of the reals). In other words, if you pick a real number at random, the resulting number will be random.

Answer by Halfdan Faber for Colloquial catchy statements encoding serious mathematics

2009-11-01T04:29:17Z

You Can’t Unscramble Scrambled Eggs

Answer by Halfdan Faber for Any news on Harada's paper that claims to prove the standard conjectures?

2009-11-01T04:20:41Z

This is the paper in question: http://www.math.uiuc.edu/K-theory/0919/

Comment by Halfdan Faber

2012-07-20T20:11:12Z

With respect to convergence of the frequency of inside zeros of n!, I see no evidence of strong convergence to $\frac{1}{10}$ for $n \to \infty$ . For n up to 10000 my analysis shows weak convergence, meaning high individual variation, but accumulated frequency deviation from $\frac{1}{10}$ varies significantly with mean zero.

Comment by Halfdan Faber

2012-04-21T04:13:00Z

@Joel, I agree wholeheartedly with your call for rigor and precision. With respect to your remarkably short attempt at contradicting definability, clearly your notion of well-ordering definability does not satisfy the normal definition of first-order definability. By your argument it follows that all members of any set are uniquely defined by virtue of the well-ordering theorem, and equivalently, invocation of AC implies not only implicit identification but also explicit definition. This is clearly incorrect. Still looking forward to studying your paper, though...

Comment by Halfdan Faber

2012-04-20T05:19:15Z

Thanks for the reference as well as the downvote. Those claims may be problematic, but at present they are the standard. Will study your paper in detail over the next days.

Comment by Halfdan Faber

2012-02-02T03:48:31Z

Induction does not reach actual infinty, but could be viewed as an example of reasoning with potential infinity. Particularly note that from $IsFinite(0)=True$ and $IsFinite(x) −> isFinite(x+1)$ we prove by induction that all natural numbers are finite.

Comment by Halfdan Faber

2011-04-25T01:56:18Z

@Julian: Thx, much. This is excellent! Here is another link:ja0hxv.calico.jp/pai/estatistics5t.html. Thanks much to Alex Yee for providing this. They found 13 zeros in positions 3,186,699,229,890 and 3,675,091,769,442. Since this is from the longest Pi calculation done so far, this is likely the longest known zero sequence. See also: numberworld.org/misc_runs/pi-5t/announce_en.html.

Comment by Halfdan Faber

2011-04-24T23:44:31Z

Scott, isn't the enumeration of all theorems of ZFC almost surely non-computable, though definable? I.e. the hard to program Turing Machine, you are suggesting would be of infinite length?

Comment by Halfdan Faber

2011-04-24T22:38:22Z

Well, if the position of first occurence for a k-length sentence grows at the same rate for all base digits, something can be learned from that. If 6-sequences of k length actually always occur first, then Pi would not be normal (I realize this is more than exceedingly unlikely to be the case, but would like to see some references).

Comment by Halfdan Faber

2011-04-24T22:30:29Z

Results from first 200,000,000 digits were found using: angio.net/pi/piquery.html.

Comment by Halfdan Faber

2010-12-06T02:50:23Z

Richard Guy's book [Unsolved Problems in Number Theory][1], pages 113-116, gives a very good account of the history of the conjecture. [1]: books.google.com/…

Comment by Halfdan Faber

2010-11-15T02:00:03Z

On a curios note, Jacob Bernoulli discovered the number e by examining $\lim_{x\rightarrow\infty}{\left(1+\frac{1}{x}\right)^x}$

Comment by Halfdan Faber

2010-10-08T04:22:22Z

I have really only added an expanding number of additional example transforms and the functional equation addendum. The question stands as originally stated. In any case I will leave it as is, and not add any additional examples.

Comment by Halfdan Faber

2010-10-03T06:47:11Z

Absolutely! Thanks again.

Comment by Halfdan Faber

2010-10-03T06:44:08Z

Well, the question was just answered and accepted. Perhaps the threat of imminent closure was the needed catalyst...

Comment by Halfdan Faber

2010-10-03T06:42:23Z

The second part of this question was also answered indirectly. There appears to have been very little, if any, work related to the BGTZ Conjecture in recent years.

Comment by Halfdan Faber

2010-10-03T06:31:19Z

Fantastic! I'm going to accept the answer, with the note from Gerry.