Wikipedia:Reference desk/Mathematics

Welcome to the mathematics section
of the Wikipedia reference desk.

skip to bottom

Select a section:

• Computing
• Entertainment
• Humanities
• Language
• Mathematics
• Science
• Miscellaneous
• Archives

Want a faster answer?

Main page: Help searching Wikipedia

   

How can I get my question answered?

• Select the section of the desk that best fits the general topic of your question (see the navigation column to the right).
• Post your question to only one section, providing a short header that gives the topic of your question.
• Type '~~~~' (that is, four tilde characters) at the end – this signs and dates your contribution so we know who wrote what and when.
• Don't post personal contact information – it will be removed. Any answers will be provided here.
• Please be as specific as possible, and include all relevant context – the usefulness of answers may depend on the context.
• Note:
  • We don't answer (and may remove) questions that require medical diagnosis or legal advice.
  • We don't answer requests for opinions, predictions or debate.
  • We don't do your homework for you, though we'll help you past the stuck point.
  • We don't conduct original research or provide a free source of ideas, but we'll help you find information you need.

Ready? Ask a new question!

How do I answer a question?

Main page: Wikipedia:Reference desk/Guidelines

• The best answers address the question directly, and back up facts with wikilinks and links to sources. Do not edit others' comments and do not give any medical or legal advice.

See also:

• Teahouse
• Help desk
• Village pump
• Help manual

October 3

Vertical bars in set theory

In this problem:

(2) Find a model 𝒥 for the following set of sentences, with |𝒥| = {1, 2, 3, 4, 5}:

1. ∀x∃yRxy

2. 𝑓(x, 𝑠(x)) = sum(1, prod(x, 2))

What do the vertical bars around the second instance of 𝒥 mean? Is it saying that {1, 2, 3, 4, 5} is the set of sentences that 𝒥 is supposed to model?

MonroeL (talk) 04:27, 3 October 2017 (UTC)

I think it's probably using |𝒥| to mean the universe of the model (sometimes called the domain, the underlying set, or the carrier). That is, your "objects" are the numbers 1 through 5.

(Note that I don't think this is very standard notation. More usually, |𝒥| would be the cardinality of the universe.) I take it back — actually I think this is reasonably standard.

I don't think there's enough information here to give a sensible answer to the problem. Are we supposed to take "sum" and "product" to have their usual meanings on 1 through 5? That doesn't make a lot of sense, given that some of the answers would not be objects of the model. So I'm not quite sure what's going on. --Trovatore (talk) 04:40, 3 October 2017 (UTC)

Thanks for the speedy response!

In this problem, the function s is the successor function, and sum and prod are the usual meanings for the terms "sum" and "product."

I just saw this information from the instructor: "you need to find a relation over |𝒥| that makes 1. true, and a function over |𝒥| that makes 2. true." I don't think that's communicated very clearly in the original problem, but it's alright!

I appreciate the help a lot. Have a great day! MonroeL (talk) 05:22, 3 October 2017 (UTC)

It's still very peculiar. For example, in the second clause, take x to be 3. Then you have 𝑓(x, 𝑠(x)) = 𝑓(3, 4) = sum(1, prod(3, 2)) = 7, if I'm following so far. But 7 is not an element of the universe of the model, so as far as I can tell this doesn't make sense. --Trovatore (talk) 05:41, 3 October 2017 (UTC)

Side comment: possibly, if the question gets answered, the answer could be added to the List of mathematical symbols...? --CiaPan (talk) 06:09, 3 October 2017 (UTC)

October 4

Are there only two types of Truth in Mathematics?

Are there only two types of Truth in Mathematics? The only two type I can think of are

Type 1: Truth in boolean algebra. Truth is denote by 1 or T and it is arbitrary constant (ie by definition). Conversely False is also an arbitrary constant.

Type 2: Truth in Proof Theory. A Mathematical statement is true if the statement that are provable in a formal axiomatic system. A statement is false if the proof leads to a contradiction. A statement is unproveable if it cannot be proven true or false.

It seems to me that the type 1 is pretty arbitrary while type 2 isn't about truth at all but merely about proveability of statement(s). Can I safely say that there are no "truths" in mathematics, where the word "truths" refers to real world certainties like "It is TRUE that the IRS expects me to pay my taxes."

110.22.20.252 (talk) 01:48, 4 October 2017 (UTC)

Well, you've completely left out truth as understood by mathematical realists (aka Platonists). For realists, mathematical truth is about the behavior of real objects, and is quite distinct from provability. --Trovatore (talk) 02:18, 4 October 2017 (UTC)

I think 2 is usually called provable rather than true, but there are schools of thought, e.g. intuitionism, which takes 2 to mean true. So statements can be true but unprovable for most people, but some would say these are statements which are not false, which is not the same as being true. Falsity has shades of meaning as well; while most say it's the other Boolean value, the intuitionists would say that a statement is only false if by assuming it you can derive a contradiction. There many flavors of non-standard logic and their study is a specialty in itself; any of them could be said to have its own interpretation of truth and falsity. Also, my understanding is that a mathematical statement must be about mathematical objects. Since the IRS is not a mathematical object, statements about it aren't mathematical statements. There are types of truth outside mathematics, e.g. scientific truth, and mathematics doesn't claim to cover everything in the universe. --RDBury (talk) 03:45, 4 October 2017 (UTC)

It's true that intuitionists take truth to equal provability, but it's important to keep in mind that they disidentify provability from provability in any fixed axiomatic system. That's the "intuition" part — the human mathematician is supposed to be able to tell what is a proof and what's not, and doesn't delegate that role to any stinking formal deductive system. --Trovatore (talk) 04:11, 4 October 2017 (UTC)

I should probably say a little more about that. It's not as arbitrary as it sounds. Here's the idea:

• A proof of A∧B is a proof of A together with a proof of B.
• A proof of A∨B is either a proof of A or a proof of B.
• A proof of ∃xP(x) is a value n together with a proof of P(n).
• A proof of ¬A is a proof of A→false.

So far this is completely judgment free. But we haven't said what to do about implication (note that A→B is not the same thing as ¬A∨B for intuitionists; if it were, the clause defining a proof of ¬A would be circular, since presumably you can't prove false). So here are the final clauses:

• A proof of A→B is a method for turning any proof of A into a proof of B.
• A proof of ∀xP(x) is a method for obtaining, for any value n, a proof of P(n).

This is where it ceases to be clearly well-defined. Generally, intuitionists do not nail themselves down as to what is meant by a "method". As I understand it, the human mathematician is supposed to understand the argument underlying the method, and agree that it does indeed turn any proof of A into a proof of B.

I was put off by that when I first encountered it, but in the end had to agree that it is not that different from what mathematicians who claim to be using the axiomatic method do in practice. They almost never actually prove things directly from the axioms. Rather, they give an argument in prose which, in principle, is supposed to be translatable into an argument from the axioms, using routine techniques, given a competent mathematician with unlimited time and patience. --Trovatore (talk) 04:38, 4 October 2017 (UTC)

Thanks for the clarification. I'm not with you on never being able to prove false though since that's basically how proof by contraction works, but hopefully you can't prove false without adding additional assumptions to the standard axioms. What you're saying about the usual practice for proof is true, but it seems to me that that will change in the next few decades as automated proof checkers gain acceptance. Btw, [1] is a rather entertaining (for an hour long lecture on mathematical logic) video covering some of these ideas. --RDBury (talk) 14:42, 4 October 2017 (UTC)

So for purposes of this discussion I'm using words like "prove" in their intuitionistic acceptions (wikt:acception; a useful word maybe not that common in English). Axioms have not been mentioned.

For intuitionists, ¬A is shorthand for A→false. A proof of ¬A is a method that, given any proof of A, would allow you to transform it into a proof of false. But presumably no proof of false exists, because then false would be true. This is the intuitionistic version of proof by contradiction.

(Occasionally people make the mistake of thinking that intuitionists don't accept proof by contradiction. That's not true — actually it's the only way you can intuitionistically prove a negative statement. It's true that they don't accept it for proving positive statements.) --Trovatore (talk) 17:39, 4 October 2017 (UTC)

Well that is rather an open question. Maybe it depends on one's point of view, and maybe it doesn't. The article Philosophy of mathematics is a start. Perhaps I could get invites on a dinner circuit by adopting the Mathematical universe hypothesis and saying we're in a superposition of worlds where undecidable results are true or false :) By the way Truth has a small section about mathematics which is like what you said, but as always philosophical questions become murkier the more you look at them. 12:41, 4 October 2017 (UTC)

MU (Markup?) key on a calculator

I recently got a "Comix CS-3136" calculator for $11.99. [2]

Mostly I wanted something with big keys, but the 16 digit display might be useful for calculating the exact size of very large sparse arrays. A 14 digit calculator can handle up to 2^46 (70,368,744,177,664 Bytes, 70TB). A 16 digit calculator can handle up to 2^53 (9,007,199,254,740,992 Bytes, 9007TB).

Mostly it acts like a normal calculator, or perhaps a 10-key adding machine, but it has a "MU" key that is poorly documented. Being curious, I tried to figure out what this key does.

It appears to be related to percent, so I started by doing an experiment with the % key

Example #1: 200 + 20% = ????

• Enter: 200 Display: 200
• Enter + Display: 200+
• Enter 20 Display: 20+
• Enter % Display: GRAND TOTAL 240=
• Enter = Display: GRAND TOTAL 440=

Yes, there is a small + or = to the right of some results, and sometimes it says GRAND TOTAL above the number.

OK, fairly normal, other than the + key working 10-key style instead of calculator style.

So I tried the same thing with MU:

Example #2: 200 + 20MU = ????

• Enter: 200 Display: 200
• Enter + Display: 200+
• Enter 20 Display: 20+
• Enter MU Display: 1100=
• Enter = Display: GRAND TOTAL 1100=

So what did the MU key just do?

If anyone has any other test they would like me to run, just let me know. --Guy Macon (talk) 17:40, 4 October 2017 (UTC)

Yes, that is hard to understand. One thought is that it determined that a markup of 20 (dollars, cents, Euros, or whatever) on a 200 unit item (same units, of course), is 10% markup. It then applied that markup to a base of 1000 units to get a price of 1100, at that markup. Not sure where you define the base, but it apparently defaults to 1000 units. StuRat (talk) 18:57, 4 October 2017 (UTC)

Just Google calculator mu. The first result is https://www.quora.com/What-does-MU-on-a-calculator-mean. PrimeHunter (talk) 20:37, 4 October 2017 (UTC)

That page say "Suppose a shopkeeper wants to sell the product at 100 after 20% discount. Then he can use mark up button. He will input 100 MU 20 % and the answer he gets is the price he will have to write on the product", So I tried it:

Example #3:

• Enter: 100 Display: 100
• Enter: MU Display: (no change)
• Enter: 20 Display: 10010
• Enter: % Display: (no change)
• Enter: = Display: GRAND TOTAL 10010=

I also am having trouble making that concept work with example 2. Mark 1100 on the item so that it sells for 200 after a 20% discount?

Hmm. Maybe I am getting the final price and the discount percentage backwards. Let's try that:

Example #4:

• Enter: 20 Display: 20
• Enter + Display: 20+
• Enter 200 Display: 200+
• Enter MU Display: 110=
• Enter = Display: GRAND TOTAL 110=

Is the above saying that if I buy an item for 200 and sell it for 220 I have a 110% markup? Would that be a useful calculation for a merchant? --Guy Macon (talk) 08:56, 5 October 2017 (UTC)

Possibly this manual http://files.sharpusa.com/Downloads/ForHome/HomeOffice/Calculators/Manuals/cal_man_CS1194H.pdf will help. It's about a calculator model(s) different from yours, but I suppose the MU key is the same "Multiple Use" function. --CiaPan (talk) 09:56, 5 October 2017 (UTC)
Forgot to ping: @Guy Macon: --CiaPan (talk) 09:59, 5 October 2017 (UTC)

Maximizing Inner Product

I have an M x 3 matrix A and a row vector <v|, I want to find |u> so that <v|A|u> is maximal. The specifics of <v| vary around, but it can be assumed that every element is positive. The elements of A and |u> are all in the interval [0, 1]. If it matters, M will never be huge, but in the vicinity of 20 to 30. While I would prefer to be able to find the true maximal |u>, and in a computationally quick way, an approximation would work, as long as it is relatively close to the actual value. I have a large data set of A's for which I will need to find |u>, for fixed <v|, for all points (numbering in the millions), so any method that takes a while (like discretely stepping through all values of |u> with elements of the form an integer / 1000, or some such, are not going to be viable due to time constraints (in this case on the order of 1000000 * 1000 * 1000 * 1000, or a quadrillion operations for the entire data set - but, if I could narrow the elements of |u> down to a much smaller interval...)). Thank you for any, and all, help:-)Phoenixia1177 (talk) 19:59, 4 October 2017 (UTC)

Since all elements of $<v|$ and $A$ are non-negative then all elements of raw vector $<v|A$ are also non-negative. Since all three elements of the column vector $|u>$ are required to be non-negative and less or equal to the unity then the column vector that maximizes the product $<v|A|u>$ is $|u>=(1,1,1)^{T}$. Ruslik_Zero 20:44, 4 October 2017 (UTC)

Oh my! I forgot a constraint, sorry about that - there is <L| = (a, b, c) so a + b + c = 1 and a, b, c are all in the unit interval. Let the transpose of the first row in A be |d>, then I need the maximal |u> from the set {|u> : <L|u> = <L|d>}. I've been mulling this over in my head for a while and this is the first time I've put it on paper, I still can't believe I left that out. Since this is an approximation problem to start with; I'd be just as happy with help on a variation (if the above is a pain), instead of this added constraint, assume that there is fixed x in (0, 1) so that given a transpose of a row in A, call it |d>, <L|d> = x, then the |u> can come from {|u> : <L|u> = x}. Either constraint does the trick, the latter is probably a better solution, but I haven't been able to test either, so I'm not sure about that. Sorry again for the confusion. (Or, for another variation,you can assume that the |u> are all a fixed distance from the transpose of A's first row, that that first row is in the interior of the unit cube, and that the fixed distance is enough that the ball around the row is within the cube as well.)Phoenixia1177 (talk) 20:57, 4 October 2017 (UTC)

October 5

Definition of Bundle Maps

I'm pretty new to Wikipedia so I'm sorry if this is the wrong place for this. On the talk page for Bundle map, I previously asked a question about the definition of the term. The article doesn't cite any sources or provide references for additional information, and no one has answered the question on that page. I thought I would repost it here to see if I can get an answer, or perhaps someone could point me in the direction of resources that would answer the question for me. Let me know if it is inappropriate to ask the same question in two places, and where the question should have been asked initially.

I was following along with the lecture series "Lectures on the Geometric Anatomy of Theoretical Physics", given by Dr. Frederic P. Schuller and freely available on YouTube. In Lecture 6, when he introduces bundle maps (about 50 minutes in), he does not include the requirement that they are continuous. I also don't see that condition included here http://mathworld.wolfram.com/BundleMap.html, but the article includes ″continuous″ in the definition. I have been unable to find other information on the topic in my brief attempt at research (it doesn't help that the article lists no references), and was wondering if someone can clarify for me. Did Dr. Schuller simply forget to say the word continuous? Or is there some reasoning for intentionally leaving it out? Are both definitions used, and it simply depends on the author? --AlfonsoAnonymous (talk) 00:37, 5 October 2017 (UTC)

In topology, "map" is generally understood to mean continuous function. In the rare case where one might allow for discontinuous functions, then one will generally specifically use "function", and possibly even say something like "not necessarily continuous" for emphasis. --Deacon Vorbis (talk) 00:56, 5 October 2017 (UTC)

More generally, the meaning of a word like 'map' might include whatever assumptions are needed in the current context. So, for example, if you're talking about smooth manifolds then a map is assumed differentiable as well. This kind of thing would probably be caught and fixed in a textbook or research paper, but it's common in the slightly less formal setting of a lecture hall. Btw, I've seen Dr. Schuller series and it's a good introduction to much of the math you need for theoretical physics. --RDBury (talk) 16:37, 5 October 2017 (UTC)

@Deacon Vorbis: I figured it would be something like that, I just wanted to double check. He is usually pretty careful about explicitly stating assumptions, so that threw me off.

@RDBury: His lectures are great! Do you happen to know of any resources (textbook, online notes, etc) that would go along with the lecture series? My university unfortunately doesn't have anyone in theoretical physics, or who specializes in these ares of math.AlfonsoAnonymous (talk) 02:53, 6 October 2017 (UTC)

I don't don't know of any resources specific to the lecture series, but you might try The Road to Reality for a more detailed look at the subject. A warning though; it's a very dense book and finishing it is quite a feat in itself, not to imply that I've actually done it myself. --RDBury (talk) 12:43, 6 October 2017 (UTC)

I there may be an influence here from the idioms of category theory. In the category of topological spaces, continuous maps are the only morphisms. So other functions may not be considered "maps" at all. It's not necessarily sloppy — it's perfectly precise, as long as everyone understands that that's how the terminology is being used. --Trovatore (talk) 20:11, 7 October 2017 (UTC)

Quick Challenge. Can your pocket calculator compute i^i

Quick challenge, take out your pocket calculator and compute i^i. Can your calculator do it? What's the answer and what's your model of calculator. 110.22.20.252 (talk) 05:36, 5 October 2017 (UTC)

My Casio from the 80's recognizes it as a series and lets me scroll through results: 0.20788, 3.8820e-04, 7.2495e-07, 1.3538e-09, 2.5281e-12, 4.7212e-15, 8.8165e-18, 1.6464e-20, 3.0746e-23, 5.7417e-26, 1.0722e-28, ... 209.149.113.5 (talk) 12:33, 5 October 2017 (UTC)

My trusty TI-83 Plus gives me only 0.2078795764. shoy (reactions) 18:13, 5 October 2017 (UTC)

My calculator can't do it. Staecker (talk) 18:33, 5 October 2017 (UTC)

The HP-48 emulator (Droid48) on my phone: (.207879576351,0). -- ToE 19:52, 5 October 2017 (UTC)

I don't have a calculator but I sometimes enter a sum into Google. Putting i^i into Google I get 0.20787957635, so it does a bit more than I expect - but I can't see how to enter complex numbers into the calculator that comes up. Dmcq (talk) 14:02, 6 October 2017 (UTC)

0.20787957635076193[3]

0.2078795763507619[4]

0.207879576350761908546955619834978770033877841631769608075... (using the principal branch of the logarithm for complex exponentiation)[5]

--Guy Macon (talk) 18:04, 7 October 2017 (UTC)

Differential equations

I had trouble with three parts of this word problem:

An outdoor decorative pond in the shape of a hemispherical tank is to be filled with water pumped into the tank through an inlet in its bottom. Suppose that the radius of the tank is R = 10 ft, that water is pumped in at a rate of π ft³⁄min, and that the tank is initially empty. As the tank fills, it loses water through evaporation. Assume that the rate of evaporation is proportional to the area A of the surface of the water and that the constant of proportionality is k = 0.01.

1a. The rate of change ⁠dV/dt⁠ of the volume of the water at time t is a net rate. Use this net rate to determine a differential equation for the height h of the water at time t. The volume of the water is V = πRh² - ⁠1/3⁠πh³, where R = 10. Express the area of the surface of the water A = πr² in terms of h.

⁠dh/dt⁠ =

1b. Solve the differential equation in part (a).

h(t) =

1c. What is h(⁠2000/3⁠)? Round your answer to three decimal places.

For problem 1c, I tried 9.9 ft, 660 ft, and 1,036.726 ft, which are all verified as incorrect. Any help would be appreciated. 147.126.10.148 (talk) 07:26, 5 October 2017 (UTC)

Sanity check - the volume of the hemisperical tank is 2000π / 3 ft³. So if we neglect evaporation, the tank will be full at time t=2000 / 3. So without evaporation h(2000 / 3) = 10 ft. When we include evaporation h(t) will be reduced, so h(2000 / 3) < 10 ft.

What equations did you get in part 1a for dV/dt and dh/dt ? Gandalf61 (talk) 10:26, 5 October 2017 (UTC)

That was my question—what is the value of h(⁠2000/3⁠) rounded to three decimal places? The equation ⁠dh/dt⁠ already accounts for evaporation. I don't have equations for either ⁠dV/dt⁠ or ⁠dh/dt⁠—I didn't know where to start. 147.126.10.152 (talk) 16:19, 5 October 2017 (UTC)

_{(presumably $k$ has units of ft/min, and has been chosen to make $\mathrm {flow} _{\mathrm {in} }-k\pi R^{2}=0$, so that the integral is easy) --catslash (talk) 16:23, 5 October 2017 (UTC)}

The derivative of volume of water is:

${\frac {dV}{dt}}=\pi -k\pi r^{2}=\pi -k\pi (2Rh-h^{2})$.

On other hand it is

${\frac {dV}{dt}}=\pi r^{2}{\frac {dh}{dt}}=\pi (2Rh-h^{2}){\frac {dh}{dt}}$.

So, from the above two equations

${\frac {dh}{dt}}={\frac {1}{2Rh-h^{2}}}-k$.

You can solve it in the general case but you can also note that $R=1/{\sqrt {k}}$. In this case the equation is greatly simplified. So, omitting details the solution is

$h={\sqrt {{\frac {k^{2}t^{2}}{4}}+{\sqrt {k}}t}}-{\frac {kt}{2}}={\frac {2}{\sqrt {k}}}{\frac {1}{\displaystyle {\sqrt {1+{\frac {4}{k^{3/2}}}{\frac {1}{t}}}}+1}}$.

So, $\lim _{t\to \infty }h=1/{\sqrt {k}}=R$ and then at $t=2R^{3}/3=2/(3k^{3/2})$ we have

$h={\frac {1}{3{\sqrt {k}}}}({\sqrt {7}}-1)={\frac {10}{3}}({\sqrt {7}}-1)\approx 5.49$

Ruslik_Zero 19:17, 5 October 2017 (UTC)

Recursive Complex Number Project

I am covering both recursive functions and complex numbers in the same week. For complex numbers, every project has to do with AC electricity. Apparently, that is the only example of real-world complex number use that any textbook writer knows about. I've been googling (drowning in thousands of pages about AC electricity examples) trying to find a real-world example that uses complex numbers and recursion so I can cover both in one project. I've found nothing. Does anyone here know of any real-world examples where complex numbers and recursion are used together? 209.149.113.5 (talk) 12:25, 5 October 2017 (UTC)

Fractals are inherently recursive, and many fractal images use complex numbers. Computing the Mandelbrot set can easily be done using recursion. --Stephan Schulz (talk) 12:34, 5 October 2017 (UTC)

• See Linear difference equation#Solution of homogeneous case and particularly the subsection "Converting complex solution to trigonometric form". The solution of a difference equation of at least the second order involves complex numbers, which can be converted into trigonometric expressions, if some of the roots of the characteristic equation are complex. Loraof (talk) 02:00, 6 October 2017 (UTC)

I agree with Loraof. There's also the explicit solution of degree 3 equations on reals, which involves complex numbers, and may have been the historically first application for them. – b_jonas 22:52, 8 October 2017 (UTC)

Eulerian Paths: Octahedron.

How many unique Eulerian (all edges visited) cycles are there on the Octahedron? (subject to rotation and mirror imaging). (vertices N, ABCD(at equator in that order clockwise)?Naraht (talk) 16:34, 5 October 2017 (UTC)

That sounds pretty rough to try to do by hand, but the number of possible paths to check is plenty small enough for a computer to brute force the solution quickly. --Deacon Vorbis (talk) 17:56, 5 October 2017 (UTC)

The problem is getting the computer to tell that two cycles are the same if one starts at position 6 of the other, and the octahedron has to be rotated and flipped to have one line up with the other. I'm trying to use the number and positions of "triangles" in the cycle and the number and positions of "over the tops" where the two vertices opposite of each other on the octahedron are in the cycle with only one vertex apart in the cycle.Naraht (talk) 20:03, 5 October 2017 (UTC)

Just divide the number you get by 48 (the size of the octahedron's symmetry group), or by 8 if you start at a given vertex (the size of a vertex's stabilizer subgroup). --Deacon Vorbis (talk) 20:35, 5 October 2017 (UTC)

48 is because you can start at any of the 6, move to any of four and then left and right are simply flipped, right?Naraht (talk) 21:40, 5 October 2017 (UTC)

It works like that here, but in general it's a little more complicated (the size of the symmetry group of the n-orthoplex is $2^{n}n!$). To explain the above a little more, the symmetry group of the octahedron acts freely on the set of Eulerian paths by virtue of it acting on the vertices of the octahedron. You're ultimately interested in the number of orbits of this action, which (since the action is free) is just the number of paths divided by the size of the group (48 in this case). --Deacon Vorbis (talk) 22:15, 5 October 2017 (UTC)

Or maybe a little more simply, every unique path will be counted 48 times, once for each element in the symmetry group. And it will always be 48 because any two different symmetries applied to a particular path will always result in a different (but symmetric) path out. --Deacon Vorbis (talk) 22:27, 5 October 2017 (UTC)

OK, that makes sense.Naraht (talk) 22:44, 5 October 2017 (UTC)

I'm guessing yoiur vertices are N ABCD and S for north and south. You didn't name the 6th one. Due to mirroring, I presume it doesn't matter if ABCD is clockwise from above or from below, just that they are in sequence. ? -- SGBailey (talk) 06:39, 6 October 2017 (UTC)

Yes, missed the S. As pointed out here, mirroring doesn't matter. Just trying to designate N and S as opposites, A and C as opposites and B and D as opposites.Naraht (talk) 15:17, 6 October 2017 (UTC)

@Naraht:, By the way, I was bored and decided to refresh my Haskell a little, so I wrote a short program that brute forced it, and came up with 186 different paths. It's still running for the 4-orthoplex. I'm not especially confident that it's going to finish in a reasonable amount of time though. --Deacon Vorbis (talk) 01:33, 7 October 2017 (UTC)

@Deacon Vorbis:, so 186*48 and then divide by the symmetry group, or did you limit it in some way? (All paths start NA and then you divide by 2)???Naraht (talk) 01:57, 7 October 2017 (UTC)

186 actual unique paths (none of which are symmetries of each other). --Deacon Vorbis (talk) 02:23, 7 October 2017 (UTC)

Oh, and it finally finished overnight (a more efficient program probably would have done this a lot faster), and it turns out there are 19244800 115468800 unique paths for the 4-orthoplex. I doubt it would be able to find the next one in a reasonable amount of time though. --Deacon Vorbis (talk) 14:11, 7 October 2017 (UTC)

My concern is not only with rotations and reflections, but also how to make sure that two pathways that start in different places in the cycle are identified with each other.Naraht (talk) 16:28, 9 October 2017 (UTC)

Well, that's probably more complicated then. Presumably you want to consider reversed traversals as the same too. In that case, even if you start at a fixed vertex, each path could potentially be counted 4 times. Unfortunately, it's not as simple as dividing by 4 (since 186 isn't divisible by 4). That means that there are some circuits where some of these symmetries happen to coincide. Now you have two different groups acting on the set of circuits: the symmetry group of the octahedron, but also D₁₂ (the dihedral group of order 24). I'm not exactly sure how to proceed in general now other than just having a computer brute-force the remainder. --Deacon Vorbis (talk) 17:14, 9 October 2017 (UTC)

Hamiltonian Dodecahedron unvisited vs. Double Hamiltonian Icoahedron unvisited.

Consider the possible sets of edges unvisited by a Hamiltonian cycle along the edges of a Dodecahedron and the possible sets of edges unvisited by a Double Hamiltonian cycle (visiting all vertices twice along the path) on the edges of a icosahedron. Are these two sets in 1-1 relationship with each other? (IN Double Hamiltonian, I'm presuming that it doesn't make a difference if the Double Hamiltonian Cycle is one cycle followed by another or if is not).Naraht (talk) 16:37, 5 October 2017 (UTC)

According to my calculations there are 30 Hamiltonian cycles on the dodecahdron, which would be the number of possible sets of unvisited edges. The second set is essentially the number of matchings on an icosohedron for which the complement is Eulerian, assuming I understand your definition of double Hamiltonian correctly. But all the complements are connected so this is just the number of matchings (by the theorem that a connected graph with every vertex of even degree is Eulerian). I get 125 such matchings, and since 30 ≠ 125 there is no one-one correspondence. It might even things up a bit to include all matchings of the dodecahedron, not just the ones whose complements are cycles, but there doesn't seem to be any reason to suspect there would be a correspondence. --RDBury (talk) 23:53, 7 October 2017 (UTC)

PS. I went ahead and verified that there are 6 matchings of the dodecahedron whose complements aren't cycles, bringing the total matchings to 36 - still a log way from 125. It's clear without actually counting them that the number must be divisible by 3, eliminating 125 as a possible value. BTW, if you're counting up to symmetry, there are are 2 matchings of the dodecahedron, and 5 for the icosahedron. --RDBury (talk) 13:03, 8 October 2017 (UTC)

October 6

Statistical significance of SHA1-prefix collisions

I have a GitHub repository in which SHA1 commit IDs from another repo are used as folder names. I've noticed that in the 75 commit folders so far, there are only 61 unique values of the first byte of the SHA1 hash; 14 values of the first byte appear twice. (Oddly, none appear three times, nor have I seen any duplication in the 12-bit prefix.) I would have expected only two or three pairs of duplicates from my intuitive understanding of the birthday paradox. What is the statistical significance of this, against the null hypothesis that the random oracle model describes the first byte of SHA1's output? If the null hypothesis is rejected, can this be explained by known weaknesses of SHA1? NeonMerlin 20:18, 6 October 2017 (UTC)

The question seems to require familiarity with a few things (GitHub, SHA-1) which probably aren't needed for the answer. The critical bit of information is the number of possible values, in this case the number of possible first bytes of the hash value. I suppose that you might assume that the first byte has 256 possible values, but the fact that they are used for folder names might mean they are encoded into ASCII somehow, reducing the number of possible values. It seems to me that without knowing the details of how GitHub turns the hash into a folder name it's impossible to eliminate that as a factor. In any case, I would think that if a weakness in the SHA-1 was that obvious then someone at the NSA would have noticed before it saw light of day; those guys are supposed to be pretty good at cryptography after all. --RDBury (talk) 00:19, 8 October 2017 (UTC)

I don't understand why you expect only two or three pairs of collisions. You usually get only 65 different first bytes from 75 objects, and getting only 61 or fewer different first bytes isn't that unusual either, it probably happens around 8% of the time. So no, it doesn't have anything to do with the cryptographical weaknesses of SHA-1.

This is all assuming you are not specifically paying attention to those first bytes of the SHA-1 values when you write into the repository. If you deliberately created or removed objects with particular first bytes in their hash, then you could line up their distribution in whatever way you want. – b_jonas 22:34, 8 October 2017 (UTC)

Let me give an explanation. Suppose that instead of creating a predetermined 75 objects, you create new objects until you get 66 different first bytes. If you already have k different first bytes, and you create a new object, then the chance that the first byte of its hash doesn't collide with any of the k first bytes you've got so far is (256−k*)/256. Thus, to jump from having k different first bytes to having *k*+1 different first bytes, you need to create on average 256/(256−k) new objects. To go from 0 first bytes to 66 first bytes then, the expected number of new objects you need to create is

256/256 + 256/255 + 256/254 + … + 256/191.

The value of that sum is approximately 76.2. (If you don't want to compute the full sum, just quickly lower bound it by grouping the terms like 26·256/256 + 20·256/230 + 20·256/210 = 26·1 + 20·1.113 + 20·1.219 = 72.6.) So you need on average more than 76 objects to get 66 different first bytes.

– b_jonas 10:48, 9 October 2017 (UTC)

To a first approximation one can consider this like a Poisson distribution for each of the 256 possibilities. The chance of no hits in a box is e^(-75/256) so we should only get about 256*(1-e^(-75/256)) different ones used - which comes out as about 65. The chance of 2 hits would be e^(-75/256)*(75/256)^2 / 2 so for all 256 we should get about 8, and for three we would expect 256*(e^(-75/256)*(75/256)^3 / 6 ) which comes out as about 1. 14 used twice instead of 8 isn't too unusual, the variance for the Poisson distribution would also be 75/256 so the standard deviation in the number of boxes would be sqrt(256*75/256) which is about 8. So I'd have thought the chances of 14 or more were even higher than b_jonas says but I could always be wrong with my finger in the air calculations. Dmcq (talk) 13:32, 9 October 2017 (UTC)

@Dmcq, I don't think modeling this with a Poisson distribution is a reasonable approximation. Recall that NeonMerlin has measured the number of total objects exactly, and got 75. If each of the boxes get a number of objects with Poisson distribution with mean 75/256, then the number of total objects you chose is a Poisson distribution with mean 75. That means you already have 0.056 probability that you chose at most 61 objects total. When that happens, it's guaranteed that you get at most 61 boxes full, but I don't see why this would explain any real phenomenon when you always take exactly 75 objects. – b_jonas 16:16, 9 October 2017 (UTC)

I computed more precise numbers, rather than the approximations from yesterday. The probability that you get 61 or fewer distinct first bytes from 75 objects is 0.08398. The following table gives C(k), the probability that you get k or fewer distinct first bytes.

k	53	54	55	56	57	58	59	60	61	62	63	64
C(k)	0.00000	0.00002	0.00007	0.00025	0.00084	0.00259	0.00720	0.01809	0.04101	0.08398	0.15538	0.26014
k	65	66	67	68	69	70	71	72	73	74	75	76
C(k)	0.39519	0.54721	0.69554	0.81982	0.90820	0.96075	0.98636	0.99631	0.99927	0.99991	0.99999	1.00000

– b_jonas 16:56, 9 October 2017 (UTC)

Yes you're quite right, I was depending on the average values approximating the proper ones. I think that assumption is near enough okay in the interest of getting something quickly to show the questioners figures were okay. However I went far too far with the variance, the end value varying affects that strongly, and I don't see how to get a nice easy estimate of that and unfortunately that is necessary to say that 61 is a reasonable value. Dmcq (talk) 19:21, 9 October 2017 (UTC)

Quoting: "256/256 + 256/255 + 256/254 + … + 256/201. The value of that sum is approximately 76.2". No, the value is approximately 63. J code:

   +/256%201+i.56
63.0564

Bo Jacoby (talk) 21:39, 9 October 2017 (UTC).

Argh. Thanks for the proofreading, Bo Jacoby. Yes, I've made a mistake in writing down two of those indexes, although I did do the right computation with the right sum. I edited in place above and underlined the changes. – b_jonas 22:33, 9 October 2017 (UTC)

Dmcq: what I should have said above is that the problem with that Poisson approximation is that it would also show that there's 0.056 chance of 61 or less distinct hashes out of 75 objects even if you took the full hash, not just the first byte, which is absurd. But I don't know any simple heuristic for estimating the variance of the number of distinct first bytes either. – b_jonas 22:43, 9 October 2017 (UTC)

October 9

Pappus's hexagon theorem

I found a proof by analytic geometry for the Pappus's hexagon theorem here. Does anyone know if it could be described any simpler? יהודה שמחה ולדמן (talk) 22:46, 9 October 2017 (UTC)

Going back to univeristy

I've suffered from a condition for a long time which affected me during school and at uni. I underachieved during A levels and did not finish my degree in Computer Science. Now I've become very interested in mathematics and have been thinking about whether I could work towards getting into a good uni, maybe even Cambridge, to study maths by retaking A levels.

Problem is I have a good idea of what maths is like at uni and I'm not sure I'd be cut out for it. It seems like you can't just memories stuff you have to have a natural ability for solving problems you've never encountered before. Unlike at school where you, for example, are shown a rule to differentiate equations and that's all you're expected to do.

It might just be that I'm not feeling very confident due to my past and the fact that I've been out of education for quite a while.

Any advice? — Preceding unsigned comment added by Polyknot (talk • contribs) 01:13, 10 October 2017 (UTC)

I certainly wouldn't advise you to major in a university subject you don't feel confident in. Sounds like you are in the British education system, but do they have something equivalent to a community college, where you can get your skills up, figure out what you want to do, and not spend much money in the process, with the idea of eventually transferring back to university when you have it all sorted out ?

As for a math field where you can just memorize formulas and apply them, maybe something more like statistics and demographics ? StuRat (talk) 01:20, 10 October 2017 (UTC)