Given an algebraic variaties of n multivarieties polynomial equations, is there any algorithm to decide whether there is n-cube inscribing to it?

And if there is, what is the computational complexity of the algorithm?

  • $\begingroup$ The WIkipedia article on the inscribed square problem says "H.W. Guggenheimer proved that every hypersurface $C^3$-diffeomorphic to the sphere $S^{n−1}$ contains $2^n$ vertices of a regular Euclidean n-cube." Perhaps this proof leads to an algorithm in this case. $\endgroup$ – Joseph O'Rourke Nov 4 '17 at 12:56
  • $\begingroup$ @JosephO'Rourke thank you, I have just read the wiki, it says that the general case is open. I think there is an algorithm, but I am not sure what tit's computational complexity is. $\endgroup$ – XL _At_Here_There Nov 4 '17 at 13:07
  • 1
    $\begingroup$ I have just found that Terrency Tao has an article and blog on the problem, terrytao.wordpress.com/2016/11/22/… But it is so long, I can not read through it ,possibly, He thinks about the problem in too complicate way. $\endgroup$ – XL _At_Here_There Nov 4 '17 at 13:32
  • $\begingroup$ terrytao.wordpress.com/2016/11/22/… $\endgroup$ – XL _At_Here_There Nov 5 '17 at 4:14
  • $\begingroup$ You might also look at Emich's result (see the above Wikipedia article), which works in the curve case for piecewise analytic curves. Varieties are always piecewise analytic (at least, at smooth points), so if you could generalize Emich... $\endgroup$ – Joshua Grochow Nov 9 '17 at 18:57

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Browse other questions tagged or ask your own question.