Wikipedia:Reference desk/Archives/Mathematics/2023 January 12

Welcome to the Wikipedia Mathematics Reference Desk Archives
The page you are currently viewing is a transcluded archive page. While you can leave answers for any questions shown below, please ask new questions on one of the current reference desk pages.

January 12

Twice more

I am looking for a mathematically enhanced person to please check User:WhatamIdoing/Sandbox 3 (permalink) and let me know (here is fine) if anything needs to be fixed. I hope this will help editors who are trying to figure out whether "doubling" is the same as "a 200% increase", but if I've screwed up the numbers, it could end up being worse than nothing. WhatamIdoing (talk) 04:51, 12 January 2023 (UTC)

Looks correct, unless I missed something. Andre🚐 05:04, 12 January 2023 (UTC)

Unfortunately I see no citations. You need those to base an article on. My guess is there is something about this somewhere, see WP:N. Also Wikipedia does not do instruction, see WP:NOTGUIDE, so it would need rephrasing to get round that. NadVolum (talk) 11:32, 12 January 2023 (UTC)

But is the intention to publish this as an article? If the purpose is to enlighten mathematically non-enhanced editors, it should find a home in user space or the Wikipedia namespace.  --Lambiam 13:48, 12 January 2023 (UTC)

I expect this to end up in Category:Wikipedia essays identifying problems and/or solutions. It's possible that it would get linked in MOS:MEDLANG or some other relevant page. WhatamIdoing (talk) 20:04, 12 January 2023 (UTC)

To me it looks like it would go on Wikibooks. I assume Wikibooks already has options for information on percentages. --RDBury (talk) 21:37, 12 January 2023 (UTC)

This is now at Wikipedia:Two times does not mean two times more. WhatamIdoing (talk) 16:42, 13 January 2023 (UTC)

Fastest-increasing possible function using imaginary numbers

Hi,

I have a friend working on a (personal, not academic) mathematical project. He asked me to find the fastest-possible increasing function for x>0. Currently this is what he has:

X= a+ib ¥ a,b € R

How can he modify this function to increase at an even faster rate? 142.127.187.55 (talk) 20:40, 12 January 2023 (UTC)

1. I do not understand the notation. The yen (or yuang) sign "¥" is used as a currency sign and has no common mathematical meaning. Is the intention, $X=a+ib~~\forall a,b\in \mathbb {R}$? This is false for all values $X\in \mathbb {C} .$
2. There are many conventional ways of defining a function, such as $f(x)=ax^{2}+bc+c,$ or $y=ax^{2}+bc+c.$ The phrase $X=a+ib$ is not one of them. What is the input to the function (aka the "argument"), and what is the output (the "value" or "result")?
3. The notion of an increasing function requires its domain and range to be ordered sets. The complex numbers are not an ordered set, so the question appears to be self-contradictory.
4. Among the fast increasing real-valued functions, there is no fastest. However fast $f(x)$ may increase as a function of $x,$ it will be outpaced by $e^{f(x)}.$  --Lambiam 21:31, 12 January 2023 (UTC)

Just an aside, one can describe the size of complex numbers, it is usually taken to be the length of the vector "z" from the origin to the point on the complex plane, such that for z = a + bi, |z| = √(a² + b²). While there are an infinite number of complex numbers of any given magnitude, though as you note, it's not possible to create an ordered set of these, as there are infinite complex numbers with any given magnitude. However, one could look at the effect of a function on the magnitude of the complex numbers in question, and perhaps do something with that? --Jayron32 13:07, 13 January 2023 (UTC)

Conventionally, the real numbers are viewed as a subset of the complex numbers, so a fast increasing real-valued function is at the same time a complex-valued function whose magnitude is fast increasing. Moreover, if $f(x)$ is a fast increasing real-valued function, the eventually strictly complex-valued function $if(x)$ also has a fast increasing magnitude. But, as before, there is always a faster one.  --Lambiam 13:55, 13 January 2023 (UTC)

you might be interested in Busy beaver which is a formalised version of the problem of finding the fastest growing function. It is yet another of these unprovable type problems but the first few grow incredibly fast. NadVolum (talk) 15:56, 13 January 2023 (UTC)

• So, I've been thinking about this, and doesn't the "fastest growing function" of whatever definition we give that, suffer from the same problems as defining the "largest possible number", i.e. any number can be surpassed by merely adding 1 to it. Any function that monotonically grows at the rate of "X" can simply be applied recursively to itself to increase the rate of growth arbitrarily, can it not? I mean, we can take something like f(x) = 2^x; can't I just define a new function g(x) such that g(x) = f(f(x)) = 2^(2^x), which now grows faster. Since I can repeat that process ad infinitum, there is no upper bound on how fast my function can grow. --Jayron32 16:44, 13 January 2023 (UTC)

True, hat's why I pointed at the busy beaver aricle which shows how one can turn the question into something more meaningful. 2^f(x) uses two more symbols than f(x). NadVolum (talk) 17:54, 13 January 2023 (UTC)

At the same time, the busy beaver function grows faster than each of the functions $2^{x},2^{2^{x}},2^{2^{2^{x}}},\,...$  --Lambiam 23:13, 13 January 2023 (UTC)

It's not really accurate to say, as NadVolum did, that the busy beaver is a "formalised version of the problem of finding the fastest growing function". What it shows is that there is a function (not itself computable) that grows faster than any computable function. There's no fastest-growing function, and there's no fastest-growing computable function, but there are noncomputable functions that grow faster than any computable function. --Trovatore (talk) 05:41, 15 January 2023 (UTC)

It is a perfectly well defined fuction even if it not computble and it gets around the problem of 2^f(x) growing faster than f(x) which needs to be got around if the question to to mean anything sensible. NadVolum (talk) 15:12, 15 January 2023 (UTC)

Huh? How does it "get around the problem"? There is no getting around that problem in any way whatsoever, and the question is perfectly meaningful, it just has the answer "there is no fastest-growing function". --Trovatore (talk) 17:00, 15 January 2023 (UTC)

Specifically, if $\lambda n\,.\Sigma (n)$ stands for the incredibly fast growing busy beaver function, the function $\lambda n\,.2^{\Sigma (n)}$ grows incredibly faster. Constructivists will dispute that the function is perfectly well defined.  --Lambiam 19:51, 16 January 2023 (UTC)

But will it grow faster than the busy beaver with that number of symbols added as extra states added to its parameter? I think you'll find just adding one to its parameter makes a function that grows faster than two to the power of the function. NadVolum (talk) 20:38, 16 January 2023 (UTC)

Got edit-conflicted saying the same thing. But of course we can easily come up with a function that grows faster than any shift of BusyBeaver. It's still true that BusyBeaver is not any sort of answer to "what is the fastest-growing function" — I still can't figure out what your point is supposed to be on that. --Trovatore (talk) 20:44, 16 January 2023 (UTC)

(ec) Might be worth pointing out, though, that while $2^{\textrm {BusyBeaver}}$ dominates ${\textrm {BusyBeaver}}$ itself, it's dominated by some shift of ${\textrm {BusyBeaver}}$.

That is, using your notation, there's some small $k\,\!$ such that $\lambda n\,.\Sigma (n+k)$ dominates $\lambda n\,.2^{\Sigma (n)}$. I expect $k=1$ but I don't have a proof. When you're talking about the Busy Beaver, a mere exponential gets lost in the noise, and it would not be unreasonable to say that $2^{\Sigma }$ doesn't so much "grow faster" than $\Sigma$ as that it has a modest head-start. --Trovatore (talk) 20:42, 16 January 2023 (UTC)

Something like $\lambda n\,.\Sigma (2^{n})$ should grow faster than anything with just the added number of symbols. It doesn't fit in as a straightforward fastest growing function with a parameter though., not like $\lambda n\,.f(\Sigma (n))$ where f is any computable function which will always be dominated by a shifted busy beaver. I wonder if it is possible to prove a shift of 1 is always enough for that eventually. NadVolum (talk) 21:05, 16 January 2023 (UTC)

As I've said a couple of times, the Busy Beaver is not any sort of "fastest-growing function". You still haven't supported that claim, or even said intelligibly what you mean by it. --Trovatore (talk) 21:19, 16 January 2023 (UTC)

Given any function that you can compute then eventualy the busy beaver function will exceed it forever. and it is straightforward to calculate a value for which that is true - it is just the size of the algorithm plus a constant. I think it would be very interesting if anyone finds something that grows faster that doesn't use the busy beaver in its definition. There may be a theorem waiting there. That seems to me a pretty good way of getting something sensible from a request for a fastest growing function rather than just giving up because adding one gives something bigger. NadVolum (talk) 23:36, 16 January 2023 (UTC)

"Given any function that you can compute then eventual[l]y the busy beaver function will exceed it forever." That's true. But so what? BB is not the fastest-growing computable function, because it's not computable. It's not the fastest-growing function, because you can easily come up with functions that grow faster. All it shows is that the computable functions are a bounded subclass of all functions (in the order of eventual domination).

As for functions that grow faster but don't refer to BB in their definition, sure I can do that. First, a little lemma: Given any countable collection of functions $f_{i}:\mathbb {N} \to \mathbb {N}$, $i\in \mathbb {N}$, there is a $g:\mathbb {N} \to \mathbb {N}$ such that $g\,\!$ eventually dominates each of the $f_{i}$. Proof: Let $g(n)=1+\mathrm {max} (\{f_{i}(n):i\leq n\})$.

Now take an oracle for the halting problem, and consider all functions from $\mathbb {N}$ to $\mathbb {N}$ that are relatively computable in that oracle. Run the above lemma to find a function that dominates them.

Now, granted, this does something rather like the Busy Beaver function, but it does not directly refer to the Busy Beaver function. --Trovatore (talk) 23:52, 16 January 2023 (UTC)

It sounds exactly like it to me NadVolum (talk) 00:05, 17 January 2023 (UTC)

Well, I think the burden is on you to explain what you mean here. --Trovatore (talk) 00:08, 17 January 2023 (UTC)

I presume you have some computable way of ordering the functions even if you don't know which ones are computable? NadVolum (talk) 00:22, 17 January 2023 (UTC)

If you have an oracle for the halting problem, you do know which ones are computable. --Trovatore (talk) 00:25, 17 January 2023 (UTC)

The oracle would have to have an input of functions to check in a particular order. If that input list is computable you're practically back to the busy beaver. Otherwise your g function has no bound for even the very first value. NadVolum (talk) 00:31, 17 January 2023 (UTC)

One might use this function of $n$: the largest natural number that can be defined by a ZFC predicate using no more than $n$ symbols – or $0$ if $n$ is not large enough to define a number. Calling it $\mathrm {Z}$, one can prove that $\mathrm {Z} (\mathrm {Z} (n))$ eventually dominates $\Sigma (n),$ but its definition is independent from the notion of a TM.  --Lambiam 00:46, 17 January 2023 (UTC)

In any case this tangent is irrelevant; I didn't say the function I was defining was computable, even relative to the halting-problem oracle (and in fact it is not). --Trovatore (talk) 01:36, 17 January 2023 (UTC)

(By the way Lambiam's suggestion is good, though a bit overkill. I assume "ZFC predicate" here is really supposed to mean "predicate in the first-order language of sets"; there's no need to specify the formal theory, just the language and its intended interpretation. You could still blow Busy Beaver out of the water using just first-order predicates in the language of arithmetic, and then (if such things bother you) you don't have to commit to definite truth values for statements about sets, but only about natural numbers. Presumably Solomon Feferman, for example, would accept that.) --Trovatore (talk) 02:15, 17 January 2023 (UTC)

I'm sorry, I should never have brought something like this up on a reference desk. I'm not altogether sure you're right in what you just said though, see Goodstein's theorem, and its see also leads to related things. NadVolum (talk) 11:43, 17 January 2023 (UTC)

You're not sure which part of it was right? I am quite sure about what I said, with the possible exception of what Feferman would have accepted. --Trovatore (talk) 17:43, 17 January 2023 (UTC)

Trovatore was absolutely right in saying that my suggestion is good. :)  The function mapping the starting value of a Goodstein sequence to the supremum of the sequence is computable. The weakness that makes Goodstein's theorem unprovable in Peano arithmetic is not a lack of expressive power. It can be formulated; it just cannot be proved from the axioms.  --Lambiam 17:50, 17 January 2023 (UTC)