Automatic Constructibility Checking of a Corpus of Geometric Construction Problems

详细信息    查看全文

• 作者：Pascal Schreck ; Pascal Mathis
• 关键词：Straightedge and compass constructions ; Regular chains ; Galois theory ; Wernick’s list
• 刊名：Mathematics in Computer Science
• 出版年：2016
• 出版时间：March 2016
• 年：2016
• 卷：10
• 期：1
• 页码：41-56
• 全文大小：679 KB
• 参考文献：1.Aubry P., Lazard D., Maza M.M.: On the theories of triangular sets. J. Symbolic Comput. 28(2), 105–124 (1999)MathSciNet CrossRef MATH
  2.Butler G., McKay J.: The transitive groups of degree up to eleven. Commun. Algebra 11(8), 863–911 (1983)MathSciNet CrossRef MATH
  3.Chen, G.: Les constructions à la règle et au compas par une méthode algébrique. Technical Report Rapport de DEA, Université Louis Pasteur (1992)
  4.Gao, X.-S., Chou, S.-C.: Solving parametric algebraic systems. In: Wang, P.S. (Ed.) Proceedings of the 1992 International Symposium on Symbolic and Algebraic Computation, ISSAC ’92, Berkeley, CA, USA, July 27–29, pp 335–341. ACM (1992)
  5.Gao X.-S., Chou S.-C.: Solving geometric constraint systems. II. A symbolic approach and decision of Rc-constructibility. Comput. Aided Des. 30(2), 115–122 (1998)CrossRef
  6.Hulpke, A.: Techniques for the computation of galois groups. In: Matzat, B.H., Greuel, G.-M., Hiss, G. (Eds.) Algorithmic Algebra and Number Theory, pp 65–77. Springer, Berlin Heidelberg (1999)
  7.Kalkbrener M.: A generalized euclidean algorithm for computing triangular representations of algebraic varieties. J. Symbolic Comput. 15(2), 143–167 (1993)MathSciNet CrossRef MATH
  8.Landau S., Miller G.L: Solvability by radicals is in polynomial time. J. Comput. Syst. Sci. 30(2), 179–208 (1985) Invited publicationMathSciNet CrossRef MATH
  9.Lebesgue, H.: Leçons sur les constructions géométriques: Gauthier-Villars, Paris. In French, re-edition by Editions Jacques Gabay, France (1950)
  10.Marinković, V., Janičić, P.: Towards understanding triangle construction problems. In: Jeuring, J. et al. (Ed.), Intelligent Computer Mathematics-CICM 2012, vol. 7362 of Lecture Notes in Computer Science. Springer (2012)
  11.Marinković, V., Janičić, P., Schreck, P.: Solving geometric construction problems supported by theorem proving. In: Francisco, B., Pedro, Q. (Eds.) Proceedings of the 10th International Workshop on Automated Deduction in Geometry, vol. TR 2014/01, pp. 121–146. University of Coimbra (2014)
  12.Meyers L.F.: Update on William Wernick’s, triangle constructions with three located points. Math. Mag. 69(1), 46–49 (1996)MathSciNet CrossRef MATH
  13.Schreck, P., Mathis, P.: Rc-constructibility of problems in Wernick’s list. In: Botana, F., Quaresma, P. (Eds.) Proceedings of the 10th International Workshop on Automated Deduction in Geometry, vol. TR 2014/01, pp. 85–104. University of Coimbra (2014)
  14.Specht, E.: Wernicks Liste (in Deutsch). Only available on the web (2009). http://​hydra.​nat.​uni-magdeburg.​de/​wernick/​
  15.Stewart I.: Galois Theory (3rd edn.). Chapman Hall, New York (2003)
  16.Ustinov A.V.: On the construction of a triangle from the feet of its angle bisectors. Forum Geometricorum 9, 279–280 (2009)MathSciNet MATH
  17.Wernick W.: Triangle constructions with three located points. Math. Mag. 55, 227–230 (1982)MathSciNet CrossRef MATH
  18.Yang, L., Zhang, J.: Searching dependency between algebraic equations: an algorithm applied to automated reasoning. In: MacKee, S., Johnson, J., Vella, A. (Eds.) Artificial Intelligence in Mathematics, pp. 147–186. Oxford University Press, Oxford (1994)
  
• 作者单位：Pascal Schreck (1)
  Pascal Mathis (1)
  
  1. ICube, UMR CNRS 7357, Université de Strasbourg, Strasbourg, France
  
• 刊物类别：Mathematics and Statistics
• 刊物主题：Mathematics
  Mathematics
  Computer Science, general
  
• 出版者：Springer Basel
• ISSN：1661-8289

文摘

Straightedge and compass constructions play a special role in geometry. First, for a very long time, they were used in practice by land surveyors or architects in order to solve concrete problems. Second, they are an inexhaustible source of exercises used to learn concepts in geometry. And finally, some famous impossible problems related to straightedge and compass constructions waited centuries before being solved using algebra. In addition, not knowing if a well-constrained problem is constructible with straightedge and compass or not, make that kind of problems more difficult to address: should we synthesize a program or on the contrary find a counterexample has to be found and treated using algebra or reduction on it? In this paper, we perform a systematic checking of a whole corpus of problems proposed by William Wernick. We expose our methodology and the algorithm we used. For each problem, its constructibility status is computed and either an algebraic argument or a geometric construction is given.