Wikipedia:Reference desk/Archives/Mathematics/2016 July 31

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.

July 31

Vincent's Theorem

In the article about Vincent's theorem it's written that "As in the case of Descartes' rule of signs if var_ab(p) = 0 it follows that ρ_ab(p) = 0". Does the second direction also hold? That is, if ρ_ab(p) = 0 it follows that var_ab(p) = 0?

This direction is important to me since I wish to perform binary search on the sign variation in order to find the roots in an interval, and the correctness of this alogrithm depends on whether both directions hold. 185.32.179.35 (talk) 10:54, 31 July 2016 (UTC)

Number of ways though *all* edges of a Hypercube?

How many ways are there to go from a single corner of a hypercube tracing every edge exactly once and back to that corner passing through each vertex twice (initial point is start, passthrough once and end (assume the corner and the orientation is fixed)?Naraht (talk) 20:06, 31 July 2016 (UTC)

Every step traverses one edge and arrives at one vertex. So to traverse every edge exactly once and arrive at every vertex exactly twice, there would have to be exactly twice as many edges as vertices. But by the chart in Hypercube#Elements, this is only true for the 4-dimensional case. So for any other number of dimensions, the number of ways is zero. Loraof (talk) 14:35, 1 August 2016 (UTC)

I agree, I tend to use hypercube to refer to only the 4-cube. To make it clear I'm asking about the Tesseract (4-cube). Since the question could be asked about any even dimensional cube, let's extend this to how many ways are there to go from a single corner of a 2n-cube tracing every edge exactly once and back to that corner passing through each vertex n times. (for n=1, the answer is 2, since you can go around the square either way.:) )Naraht (talk) 18:12, 1 August 2016 (UTC)

I can't get any insight about this, except the trivial observation that in n dimensions the number of routes is divisible by n — you say the two routes aroung the square count as separate routes; in the n-dimensional case, the starting point has n edges emerging from it, so any path can be replicated in n different ways by going out from the starting point in any of n different directions. Loraof (talk) 03:30, 2 August 2016 (UTC)

So divisible by 4 (and divisible by 3 as well since the outgoing edges from the first node other than starting are all equivalent).Naraht (talk) 14:52, 2 August 2016 (UTC)

• First of all, everyone probably knows it, but this is not actually a 4D-geometry problem, but a graph theory one (see Hamiltonian path and Eulerian path).

The amount of passages by each vertex is not really relevant, as the two passages are assured if one uses every edge once and only once (since the vertices all have connectivity 4). So the question is "simply" to count the number of Eulerian paths on the tesseract. A web search for that led me to [1] which mentions the BEST-theorem. The product is simply $(4-1)^{16}$ but the constant in front of it is (from another search) the number of arborescences, which is obviously the hard part to compute here. Tigraan^{Click here to contact me} 16:07, 2 August 2016 (UTC)

• t(G) is calculated using Kirchhoff's theorem from the Laplacian matrix, and according to this article, the Laplacian matrix for a hypercube is relatively easy to calculate. From that approach, I get a value of t(G) = 42467328 (which seems to match the value Mathworld gives for the number of spanning trees on a hypercube graph). So assuming I haven't misinterpreted anything (always possible!), the solution given by the BEST theorem is 1,828,079,220,031,488. It's a big number, but graph theory problems on hypercubes always seem to involve big numbers. Smurrayinchester 09:29, 5 August 2016 (UTC)

(edit conflict): While it certainly seems plausible, do you have a proof that there are any valid routes in the 4-dimensional case? Loraof (talk) 16:46, 2 August 2016 (UTC)

Rephrase and comments

So properly in Graph theory, the question is "How many Eulerian cycles are there in the hypercube graph Q_r?" And we know that there is at least one by the theorems at Eulerian path#Constructing Eulerian trails and circuits and information on what is known about counts is at Eulerian_path#Counting_Eulerian_circuits. Which doesn't appear to be much...

Just to repeat what I posted above: using the BEST theorem, the answer seems to be 1,828,079,220,031,488. Smurrayinchester 08:01, 6 August 2016 (UTC)

Notation for repeated exponentiation

Is there some standard notation for the function $f:\mathbb {N} \times \mathbb {R} \times \mathbb {R}$ defined recursively by $f(0,x,y)=y,f(n+1,x,y)=x^{f(n,x,y)}$?

That is, to find $f(n,x,y)$, start with y and perform the operation $t\mapsto x^{t}$ n times.

If $x=y$ then this is simply tetration, expressible for example by Knuth's up-arrow notation: $f(n,x,x)=x\uparrow \uparrow (n+1)$. But I don't know how to denote the result when $x\neq y$.

If there is no standard notation for this, what is the most concise way to describe some value $f(n,x,y)$ by combining more elementary standard notation?

Thanks. -- Meni Rosenfeld (talk) 22:21, 31 July 2016 (UTC)