On a cube and subspace projections

A. A. Boykov   ; A. V. Seliverstov

Vestnik Udmurtskogo universiteta. Matematika, mehanika, kompʹûternye nauki, Tome 33 (2023) no. 3, pp. 402-415

Résumé

We consider the arrangement of vertices of a unit multidimensional cube, an affine subspace, and its orthogonal projections onto coordinate subspaces. Upper and lower bounds on the subspace dimension are given under which some orthogonal projection always preserves the incidence relation between the subspace and cube vertices. Some oblique projections are also considered. Moreover, a brief review of the history of the development of multidimensional descriptive geometry is given. Analytic and synthetic methods in geometry diverged since the 17th century. Although both synthesis and analysis are tangled, from this time forth many geometers as well as engineers keep up a nice distinction. One can find references to the idea of higher-dimensional spaces in the 18th-century works, but proper development has been since the middle of the 19th century. Soon such works have appeared in Russian. Next, mathematicians generalized their theories to many dimensions. Our new results are obtained by both analytic and synthetic methods. They illustrate the complexity of pseudo-Boolean programming problems because reducing the problem dimension by orthogonal projection meets obstacles in the worst case.

Détail

Keywords: multidimensional cube, affine subspace, projection, discrete optimization, history of mathematics.

Bibliographie

[1] Seliverstov A.V., “Binary solutions to large systems of linear equations”, Prikladnaya Diskretnaya Matematika, 2021, no. 52, 5–15 (in Russian) | DOI | MR

[2] Antonopoulos A., Pagourtzis A., Petsalakis S., Vasilakis M., “Faster algorithms for $k$-subset sum and variations”, Journal of Combinatorial Optimization, 45:1 (2023), 24 | DOI | MR | Zbl

[3] Cacchiani V., Iori M., Locatelli A., Martello S., “Knapsack problems — An overview of recent advances. Part I: Single knapsack problems”, Computers and Operations Research, 143 (2022), 105692 | DOI | MR | Zbl

[4] Cacchiani V., Iori M., Locatelli A., Martello S., “Knapsack problems — An overview of recent advances. Part II: Multiple, multidimensional, and quadratic knapsack problems”, Computers and Operations Research, 143 (2022), 105693 | DOI | MR | Zbl

[5] D’Ambrosio C., Laureana F., Raiconi A., Vitale G., “The Knapsack Problem with forfeit sets”, Computers and Operations Research, 151 (2023), 106093 | DOI | MR

[6] Jozefiak A., Shepherd F.B., Weninger N., “A knapsack intersection hierarchy”, Operations Research Letters, 51:1 (2023), 72–78 | DOI | MR

[7] Alon T., Halman N., “Strongly polynomial FPTASes for monotone dynamic programs”, Algorithmica, 84:10 (2022), 2785–2819 | DOI | MR

[8] Leontiev V.K., Gordeev E.N., “On the number of solutions to a system of Boolean equations”, Automation and Remote Control, 82:9 (2021), 1581–1596 | DOI | DOI | MR | Zbl

[9] Gordeev E.N., Leont’ev V.K., “On the number of solutions to linear Diophantine equation and Frobenius problem”, Computational Mathematics and Mathematical Physics, 62:9 (2022), 1413–1423 | DOI | MR

[10] Handbook of incidence geometry: Buildings and foundations, ed. Buekenhout F., North Holland, 1995 | DOI | MR | Zbl

[11] Petunin A.A., Chentsov A.G., Chentsov P.A., “Some applications of optimization routing problems with additional constraints”, Vestnik Udmurtskogo Universiteta. Matematika. Mekhanika. Komp’yuternye Nauki, 32:2 (2022), 187–210 | DOI | MR | Zbl

[12] Chentsov A.G., Chentsov A.A., “Dynamic programming and questions of solvability of route bottleneck problem with resource constraints”, Vestnik Udmurtskogo Universiteta. Matematika. Mekhanika. Komp’yuternye Nauki, 32:4 (2022), 569–592 (in Russian) | DOI | MR | Zbl

[13] Devadoss S.L., Harvey M., “Unfoldings and nets of regular polytopes”, Computational Geometry, 111 (2023), 101977 | DOI | MR | Zbl

[14] Rozenfel’d B.A., Yushkevich A.P., “Geometry”, History of mathematics, v. 3, Nauka, Moscow, 1970, 153–221 | MR

[15] Polo-Blanco I., “Alicia Boole Stott, a geometer in higher dimension”, Historia Mathematica, 35:2 (2008), 123–139 | DOI | MR | Zbl

[16] Gulak N., Essay on geometry of four dimensions. Synthetic geometry, S.G. Melikov publ., Tiflis, 1877

[17] Lorenat J., “Synthetic and analytic geometries in the publications of Jakob Steiner and Julius Plücker (1827–1829)”, Archive for History of Exact Sciences, 70:4 (2016), 413–462 | DOI | MR | Zbl

[18] Del Centina A., “Desargues’s concepts of involution and transversal, their origin, and possible sources of inspiration”, Archive for History of Exact Sciences, 76:6 (2022), 573–622 | DOI | MR | Zbl

[19] Cerroni C., “Non-Desarguian geometries and the foundations of geometry from David Hilbert to Ruth Moufang”, Historia Mathematica, 31:3 (2004), 320–336 | DOI | MR | Zbl

[20] Vorob’eva V.P., Zelenaya A.E., Lutsyk V.I., “Using a 3D computer model of the $T$–$x$–$y$ diagram of the ZrO$_2$–SiO$_2$–Al$_2$O$_3$ system to resolve contradictions in the initial experimental data”, Russian Journal of Inorganic Chemistry, 66:6 (2021), 894–901 | DOI | DOI | MR

[21] Vorob’eva V.P., Zelenaya A.E., Lutsyk V.I., Sineva S.I., Starykh R.V., Novozhilova O.S., “High-temperature area of the Fe–Ni–Co–Cu phase diagram: experimental study and computer design”, Journal of Phase Equilibria and Diffusion, 42:2 (2021), 175–193 | DOI | MR

[22] Lutsyk V.I., Vorob’eva V.P., Zelenaya A.E., Lamueva M.V., “3D computer model of the Co–Cu–CoS–Cu$_2$S subsystem $T$–$x$–$y$ diagram above $800^{\mathrm{o}}$C”, Journal of Mining and Metallurgy, Section B: Metallurgy, 57:3 (2021), 319–329 | DOI

[23] Fedorov E.S., “Operations graphiques avec quatre variables independantes”, Bulletin de l’Academie des Sciences de Russie. VI serie, 12:7 (1918), 615–624 (in Russian)

[24] Lodochnikov V.N., “The simplest ways to represent multicomponent systems”, Izvestiya Instituta Fiziko-Khimicheskogo Analiza, 2:2 (1924), 255–351 (in Russian)

[25] Radiščev V.P., “Méthodes de représentation des systèmes à six composants dans les projections des figures régulières polydimensionales”, Annales du Secteur d'Analyse Physico-Chimique, 2:2 (1941), 153–173 (in Russian)

[26] Vachnadze G.A., “Some problems of descriptive geometry of four-dimensional space”, Trudy Gruzinskogo Politekhnicheskogo Instituta, 1955, no. 2(37), 193–214 (in Russian) https://cat.webtute.ru/pub.php?id=9401

[27] Mordukhai-Boltovskii D.D., “Parallelism and perpendicularity of straight lines, planes and hyperplanes in three-dimensional and four-dimensional Lobachevskii spaces”, Uspekhi Matematicheskikh Nauk, 6:4(44) (1951), 176–183 (in Russian) | MR

[28] Pervikova V.N., Naumovich N.V., Dmitrenko G.E., Zaytseva E.P., Podylina M.G., “Multidimensional descriptive geometry and geometric methods for studying multicomponent systems”, Trudy Moskovskogo Nauchno-Metodicheskogo Seminara po Nachertatel’noi Geometrii i Inzhenernoi Grafike [Issue 3], Trudy Moskovskogo Aviatsionnogo Instituta Imeni S. Ordzhonikidze, 242, Moscow Aviation Institute, Moscow, 1972 (in Russian) https://cat.webtute.ru/pub.php?id=2333

[29] Dzhaparidze I.S., “Independent planar models of four-dimensional space”, Trudy Gruzinskogo Politekhnicheskogo Instituta, 1965, no. 1(99), 31–46 (in Russian) https://cat.webtute.ru/pub.php?id=9565

[30] Dzhaparidze I.S., Descriptive geometry in the light of geometric modeling, Ganatleba, Tbilisi, 1983

[31] Filippov P.V., Descriptive geometry of multidimensional space and its applications, Leningrad State University, Leningrad, 1979

[32] Val’kov K.I., “On the interpretation of projective transformations of the four-dimensional space in the two-dimensional plane”, XVIII Nauchnaya Konferentsiya Leningradskogo Inzhenerno-Stroitel’nogo Instituta. Doklady, trudy i sborniki konferentsii LISI, 18, Leningrad Institute of Civil Engineering, Leningrad, 1960, 55–60 https://cat.webtute.ru/pub.php?id=9806

[33] Skopets Z.A., Peklich V.A., “Symplectic geometry, and Lie circular transformations”, Izvestiya Vysshikh Uchebnykh Zavedenii. Matematika, 1973, no. 1, 91–98 (in Russian)

[34] Peklich V.A., Higher descriptive geometry, ASV, Moscow, 2000

[35] Volkov V.Ya., Chizhik M.A., Graphic optimization models of multifactorial processes, Omsk State Institute of Service, Omsk, 2009

[36] Voloshinov D.V., Constructive geometric modeling: theory, practice, automation, LAP Lambert Academic Publishing, Saarbrücken, 2011

[37] Vertinskaya N.D., Mathematical modeling of multifactorial and multiparameter processes in multicomponent systems based on constructive geometry, Irkutsk State Technical University, Irkutsk, 2009

[38] Boykov A.A., Shulajkin D.A., “Visualization of geometric figures and relations of a complex plane by means of computer graphics”, Problemy Kachestva Graficheskoi Podgotovki Studentov v Tekhnicheskom Vuze: Traditsii i Innovatsii, 1 (2019), 72–93 (in Russian)

[39] Boykov A.A., Orlova E.V., Chernova A.V., Shkilevich A.A., “Creating fractal images for design and polygraphy and some geometric generalizations associated with them”, Problemy Kachestva Graficheskoi Podgotovki Studentov v Tekhnicheskom Vuze: Traditsii i Innovatsii, 1 (2019), 325–339 (in Russian)

[40] Kogabaev N.T., “On closure of configurations in freely generated projective planes”, Siberian Electronic Mathematical Reports, 18:1 (2021), 358–368 | DOI | MR