{ "type": "Article", "authors": [ { "type": "Person", "familyNames": [ "Th.", "Rassias" ], "givenNames": [ "Michael" ] } ], "identifiers": [], "references": [ { "type": "Article", "id": "bib-bib1", "authors": [], "title": "\nL. Tóth, Multiplicative arithmetic functions of several variables: a\nsurvey. In Mathematics without boundaries (Th. M. Rassias and P. M. Pardalos, eds.), Springer, New York,\n483–514 (2014) ", "url": "https://doi.org/10.1007/978-1-4939-1106-6_19" }, { "type": "Article", "id": "bib-bib2", "authors": [], "title": "\nL. Tóth, Proofs, generalizations and analogs of Menon’s identity: a survey.\n(2021), arXiv:2110.07271", "url": "https://arxiv.org/abs/2110.07271" } ], "title": "Solved and unsolved problems", "meta": {}, "content": [ { "type": "Paragraph", "id": "p1", "content": [ "The present column is devoted to\ngeometry/topology." ] }, { "type": "Heading", "id": "S1", "depth": 1, "content": [ "I Six new problems – solutions solicited" ] }, { "type": "Paragraph", "id": "S1.p1", "content": [ "Solutions will appear in a subsequent issue." ] }, { "type": "Heading", "id": "S1.SSx1", "depth": 2, "content": [ "276" ] }, { "type": "Paragraph", "id": "S1.SSx1.p1", "content": [ "Consider the tiling of the plane by regular hexagon tiles, with centers in the lattice ", { "type": "MathFragment", "mathLanguage": "mathml", "text": "L", "meta": { "altText": "L" } }, " of all\n", { "type": "MathFragment", "mathLanguage": "mathml", "text": "ℤ", "meta": { "altText": "\\mathbb{Z}" } }, "-linear combinations of the vectors ", { "type": "MathFragment", "mathLanguage": "mathml", "text": "(1,0)", "meta": { "altText": "(1,0)" } }, " and ", { "type": "MathFragment", "mathLanguage": "mathml", "text": "(−12,32)", "meta": { "altText": "\\bigl(-\\frac{1}{2},\\frac{\\sqrt{3}}{2}\\bigr)" } }, ". Glue all\nbut finitely many tiles into position, remove the unglued tiles to form a region, discard some of these tiles, and\narrange the remaining ", { "type": "MathFragment", "mathLanguage": "mathml", "text": "n", "meta": { "altText": "n" } }, " unglued tiles in the region without rotating them, in arbitrary positions such that none of\nthe tiles overlap. Is there a way to slide the unglued tiles within the region, keeping them upright and\nnon-overlapping, so that their centers all end up in ", { "type": "MathFragment", "mathLanguage": "mathml", "text": "L", "meta": { "altText": "L" } }, "?" ] }, { "type": "Paragraph", "id": "S1.SSx1.p2", "content": [ { "type": "Emphasis", "content": [ "Hannah Alpert (Department of Mathematics and Statistics, Auburn University, USA)" ] } ] }, { "type": "Heading", "id": "S1.SSx2", "depth": 2, "content": [ "277" ] }, { "type": "Paragraph", "id": "S1.SSx2.p1", "content": [ "Find\ntwo non-homeomorphic topological spaces ", { "type": "MathFragment", "mathLanguage": "mathml", "text": "A", "meta": { "altText": "A" } }, " and ", { "type": "MathFragment", "mathLanguage": "mathml", "text": "B", "meta": { "altText": "B" } }, " such that\ntheir products with the interval, ", { "type": "MathFragment", "mathLanguage": "mathml", "text": "A×[0,1]", "meta": { "altText": "A\\times[0,1]" } }, " and ", { "type": "MathFragment", "mathLanguage": "mathml", "text": "B×[0,1]", "meta": { "altText": "B\\times[0,1]" } }, ", are homeomorphic." ] }, { "type": "Paragraph", "id": "S1.SSx2.p2", "content": [ { "type": "Emphasis", "content": [ "Guillem Cazassus (Mathematical Institute, University of Oxford, UK)" ] } ] }, { "type": "Heading", "id": "S1.SSx3", "depth": 2, "content": [ "278" ] }, { "type": "Paragraph", "id": "S1.SSx3.p1", "content": [ "What is the topology of the space of straight lines in the plane?" ] }, { "type": "Paragraph", "id": "S1.SSx3.p2", "content": [ { "type": "Emphasis", "content": [ "Guillem Cazassus (Mathematical Institute, University of Oxford, UK)" ] } ] }, { "type": "Heading", "id": "S1.SSx4", "depth": 2, "content": [ "279" ] }, { "type": "Paragraph", "id": "S1.SSx4.p1", "content": [ "In the standard twin paradox, Greg stays at home whilst John travels across space. John finds, upon\nreturning, that he has aged less than Greg. This is an apparent paradox because of the symmetry in the situation: in\nJohn’s rest frame, it seems like Greg is doing the moving and so should also be experiencing time dilation. The\nstandard explanation of the paradox is that there is no symmetry: at some point John needs to turn around (accelerate),\nso, unlike Greg, John’s rest frame is not inertial for all times. So let’s modify the set-up: suppose that space-time\nis a cylinder (space is a circle). Now, John eventually comes back to where he started without needing to decelerate or\naccelerate. In this fleeting moment of return, as the twins pass one another, who has aged more?" ] }, { "type": "Paragraph", "id": "S1.SSx4.p2", "content": [ { "type": "Emphasis", "content": [ "Jonny Evans (Department of Mathematics and Statistics, University of Lancaster, UK)" ] } ] }, { "type": "Heading", "id": "S1.SSx5", "depth": 2, "content": [ "280" ] }, { "type": "Paragraph", "content": [ "The ", { "type": "Emphasis", "content": [ { "type": "MathFragment", "mathLanguage": "mathml", "text": "k", "meta": { "altText": "k" } }, "-dilation" ] }, " of a piecewise smooth map is the degree to which it stretches\n", { "type": "MathFragment", "mathLanguage": "mathml", "text": "k", "meta": { "altText": "k" } }, "-dimensional area. Formally, for a map ", { "type": "MathFragment", "mathLanguage": "mathml", "text": "f:U→V", "meta": { "altText": "f\\colon U\\to V" } }, " between subsets ", { "type": "MathFragment", "mathLanguage": "mathml", "text": "U⊆ℝm", "meta": { "altText": "U\\subseteq\\mathbb{R}^{m}" } }, " and ", { "type": "MathFragment", "mathLanguage": "mathml", "text": "V⊆ℝn", "meta": { "altText": "V\\subseteq\\mathbb{R}^{n}" } }, ", or\nmore generally between Riemannian manifolds," ] }, { "type": "MathBlock", "id": "S1.Ex1", "mathLanguage": "mathml", "text": "Dilk⁡(f)=sup{|Λk⁢D⁢fx|∣x∈U},", "meta": { "altText": "\\operatorname{Dil}_{k}(f)=\\sup\\{\\lvert\\Lambda^{k}Df_{x}\\rvert\\mid x\\in U\\}," } }, { "type": "Paragraph", "content": [ "where ", { "type": "MathFragment", "mathLanguage": "mathml", "text": "Λk⁢D⁢fx:Λk⁢Tx⁢U→Λk⁢Tf⁢(x)⁢V", "meta": { "altText": "\\Lambda^{k}Df_{x}\\colon\\Lambda^{k}T_{x}U\\to\\Lambda^{k}T_{f(x)}V" } }, " is the induced map on the ", { "type": "MathFragment", "mathLanguage": "mathml", "text": "k", "meta": { "altText": "k" } }, "-th exterior power and\n", { "type": "MathFragment", "mathLanguage": "mathml", "text": "|⋅|", "meta": { "altText": "\\lvert{\\,\\cdot}\\,\\rvert" } }, " is the operator norm. A map of rank ", { "type": "MathFragment", "mathLanguage": "mathml", "text": "k−1", "meta": { "altText": "k-1" } }, " has ", { "type": "MathFragment", "mathLanguage": "mathml", "text": "k", "meta": { "altText": "k" } }, "-dilation zero, so this can be thought of\nas a quantitative refinement of rank." ] }, { "type": "Paragraph", "id": "S1.SSx5.p2", "content": [ "Consider the rectangular prism ", { "type": "MathFragment", "mathLanguage": "mathml", "text": "Rε=[0,1]2×[0,ε]", "meta": { "altText": "R_{\\varepsilon}=[0,1]^{2}\\times[0,\\varepsilon]" } }, "." ] }, { "type": "Paragraph", "content": [] }, { "type": "List", "items": [ { "type": "ListItem", "content": [ { "type": "Paragraph", "id": "S1.I1.i1.p1", "content": [ "Let ", { "type": "MathFragment", "mathLanguage": "mathml", "text": "f:R1→Rε", "meta": { "altText": "f\\colon R_{1}\\to R_{\\varepsilon}" } }, " be a map of ", { "type": "Emphasis", "content": [ "relative degree" ] }, { "type": "MathFragment", "mathLanguage": "mathml", "text": "1", "meta": { "altText": "1" } }, ", that\nis, it restricts to a degree-", { "type": "MathFragment", "mathLanguage": "mathml", "text": "1", "meta": { "altText": "1" } }, " map between the boundaries of the rectangles.\nShow that the ", { "type": "MathFragment", "mathLanguage": "mathml", "text": "2", "meta": { "altText": "2" } }, "-dilation of such a map is bounded below by a ", { "type": "MathFragment", "mathLanguage": "mathml", "text": "0\" display=\"inline\">C>0", "meta": { "altText": "C>0" } }, " which\ndoes not depend on ", { "type": "MathFragment", "mathLanguage": "mathml", "text": "ε", "meta": { "altText": "\\varepsilon" } }, "." ] } ] }, { "type": "ListItem", "content": [ { "type": "Paragraph", "id": "S1.I1.i2.p1", "content": [ "Now let ", { "type": "MathFragment", "mathLanguage": "mathml", "text": "cε", "meta": { "altText": "c_{\\varepsilon}" } }, " be the minimum ", { "type": "MathFragment", "mathLanguage": "mathml", "text": "2", "meta": { "altText": "2" } }, "-dilation of a surjective map\n", { "type": "MathFragment", "mathLanguage": "mathml", "text": "f:R1→Rε", "meta": { "altText": "f\\colon R_{1}\\to R_{\\varepsilon}" } }, ". Construct examples to show that ", { "type": "MathFragment", "mathLanguage": "mathml", "text": "cε→0", "meta": { "altText": "c_{\\varepsilon}\\to 0" } }, " as\n", { "type": "MathFragment", "mathLanguage": "mathml", "text": "ε→0", "meta": { "altText": "\\varepsilon\\to 0" } }, "." ] } ] } ], "order": "Ascending", "meta": { "listType": "order" } }, { "type": "Paragraph", "id": "S1.SSx5.p4", "content": [ { "type": "Emphasis", "content": [ "Fedor (Fedya) Manin (Department of Mathematics, University of California, Santa Barbara, USA)" ] } ] }, { "type": "Heading", "id": "S1.SSx6", "depth": 2, "content": [ "281" ] }, { "type": "Paragraph", "id": "S1.SSx6.p1", "content": [ "Given a triangle in the (real or complex) plane, show that there is a natural bijection between the\nset of smooth conics passing through the vertices and the set of lines avoiding the vertices." ] }, { "type": "Paragraph", "id": "S1.SSx6.p2", "content": [ { "type": "Emphasis", "content": [ "Jack Smith (St John’s College, University of Cambridge, UK)" ] } ] }, { "type": "Heading", "id": "S2", "depth": 1, "content": [ "II Open problems" ] }, { "type": "Paragraph", "id": "S2.p1", "content": [ { "type": "Emphasis", "content": [ "by Dennis Sullivan (Mathematics Department, Stony Brook University; and City University of New York Graduate Center, New York, USA)" ] } ] }, { "type": "Heading", "id": "S2.SSx1", "depth": 2, "content": [ "A new problem and a new conjecture in four dimensions" ] }, { "type": "Paragraph", "id": "S2.SSx1.p1", "content": [ "Closed oriented two-manifolds were understood in Riemann’s time. Klein\ndiscovered closed non-orientable\ntwo-manifolds in the 1880s. Poincaré discovered that three-manifolds were complicated around 1900. Dimensions\nfour, five and more were then evidently even more mysterious." ] }, { "type": "Paragraph", "id": "S2.SSx1.p2", "content": [ "Therefore, it came as a surprise in the 1950s that closed manifolds oriented or non-orientable up to cobounding such a\nmanifold of one higher dimension could be completely understood in terms of numerical invariants called Pontryagin\nnumbers (integers) and Stiefel–Whitney numbers (integers modulo two)." ] }, { "type": "Paragraph", "id": "S2.SSx1.p3", "content": [ { "type": "Emphasis", "content": [ "Rochlin" ] }, ",\nmentored by ", { "type": "Emphasis", "content": [ "Pontryagin" ] }, ", began the pattern by showing in dimension four that the cobordism\nclasses of oriented closed smooth manifolds form an infinite cyclic group. The integer invariant, called the\nsignature, attached to ", { "type": "MathFragment", "mathLanguage": "mathml", "text": "M4", "meta": { "altText": "M^{4}" } }, " was computed from the intersection of two-cycles in ", { "type": "MathFragment", "mathLanguage": "mathml", "text": "M4", "meta": { "altText": "M^{4}" } }, " as the difference between the\nnumber of positive squares and the number of negative squares of the symmetric intersection form. Rochlin proved\nthe formula “the signature equals one-third the first Pontryagin number.”\n" ] }, { "type": "Paragraph", "id": "S2.SSx1.p4", "content": [ { "type": "Emphasis", "content": [ "Thom" ] }, " extended this Rochlin pattern to all dimensions using the geometric techniques of Pontryagin and\nRochlin plus the algebraic topology techniques of ", { "type": "Emphasis", "content": [ "Serre" ] }, ", showing that, up to two-torsion, the class of an\noriented manifold was determined by the set of Pontryagin numbers, these being the evaluation of products of\nPontryagin classes on the fundamental homology class of the oriented manifold. Thom also showed that the non-oriented\ntheory gave a beautiful structure determined by the Stiefel–Whitney numbers." ] }, { "type": "Paragraph", "id": "S2.SSx1.p5", "content": [ { "type": "Emphasis", "content": [ "Hirzebruch" ] }, ", using Thom’s work, extended Rochlin’s formula for the signature in a rich but explicit fashion to\nall dimensions; for example, in dimension 8 the signature is one 45th of (seven times the second Pontryagin number\nminus the evaluation of the first Pontryagin class squared on the fundamental class of the manifold)." ] }, { "type": "Paragraph", "id": "S2.SSx1.p6", "content": [ { "type": "Emphasis", "content": [ "Milnor" ] }, " used the seven in that formula to show that the seven-sphere has at least seven different smooth\nstructures. The final answer is 28, where the factor of four is related to the Dirac operator continuation of\nRochlin’s contribution discussed below. The figure shows one construction of Milnor’s generating exotic seven-sphere,\nwhich is done by taking the boundary of the eight-manifold obtained by connecting up like party rings tangent\ndisk bundles of the four-sphere as in the ", { "type": "MathFragment", "mathLanguage": "mathml", "text": "E8", "meta": { "altText": "E_{8}" } }, { "type": "Emphasis", "content": [ "Dynkin" ] }, " diagram.\n" ] }, { "type": "Heading", "id": "S2.SSx2", "depth": 2, "content": [ "Back to dimension four" ] }, { "type": "Paragraph", "id": "S2.SSx2.p1", "content": [ "Rochlin’s cobordism result depended on showing first that the cobordism group in dimension four was determined by the\nvalue of the first Pontryagin class evaluated on the fundamental class of the manifold. Then secondly showing that\nthe signature of any bounding manifold had to be zero. This last proposition is elementary, yet one of the most\nimportant facts in manifold\ntopology." ] }, { "type": "Heading", "id": "S2.SSx3", "depth": 2, "content": [ "But the most profound point comes now" ] }, { "type": "Paragraph", "id": "S2.SSx3.p1", "content": [ "Rochlin also calculated by a geometric argument à la Pontryagin that if ", { "type": "MathFragment", "mathLanguage": "mathml", "text": "M4", "meta": { "altText": "M^{4}" } }, " was almost parallelizable, i.e.,\nparallelizable in the complement of a point, then the first Pontryagin number was actually divisible by 48.\nThus\nthe signature of such a closed four-manifold, which Rochlin proved was one third of the first Pontryagin number,\nhad to be divisible by 16. This divisibility by 16 is the celebrated ", { "type": "Emphasis", "content": [ "Rochlin’s theorem" ] }, " about almost\nparallelizable smooth four-manifolds." ] }, { "type": "Paragraph", "id": "S2.SSx3.p2", "content": [ "This was at first glance a curious result for the following reason: being almost parallelizable for an oriented\nclosed four-manifold meant exactly that the self-intersection number of any mod two two-cycle was zero mod two, the\nvalue mod two being determined by evaluating the second Stiefel–Whitney class on the cycle." ] }, { "type": "Paragraph", "id": "S2.SSx3.p3", "content": [ "The intersection form for integral cycles up to homology was non-degenerate over the integers by Poincaré duality.\nSuch even-on-the-diagonal unimodular forms inside all symmetric bilinear forms taking integral values were studied in\nnumber theory. There it was known these properties meant the signature was divisible by eight and by no more in\ngeneral. A basic example is the ", { "type": "MathFragment", "mathLanguage": "mathml", "text": "E8", "meta": { "altText": "E_{8}" } }, " matrix, where the (inner) products for a special basis are illustrated by\nthe ", { "type": "MathFragment", "mathLanguage": "mathml", "text": "E8", "meta": { "altText": "E_{8}" } }, " Dynkin diagram:" ] }, { "type": "Figure", "id": "S2-SSx3-fig1", "content": [ { "type": "ImageObject", "contentUrl": "163-FIG-1.png", "mediaType": "image/png", "meta": { "inline": false } } ] }, { "type": "Paragraph", "id": "S2.SSx3.p4", "content": [ "Each nodal basis element has self-intersection number two and two nodal basis elements intersect exactly once if and\nonly if there is an edge between them, otherwise the inner product is zero. ", { "type": "MathFragment", "mathLanguage": "mathml", "text": "E8", "meta": { "altText": "E_{8}" } }, " is an even unimodular symmetric form\nof signature eight." ] }, { "type": "Paragraph", "id": "S2.SSx3.p5", "content": [ "One knows that ", { "type": "MathFragment", "mathLanguage": "mathml", "text": "E8", "meta": { "altText": "E_{8}" } }, " generates the indefinite even unimodular forms, in the sense that any such form is a direct sum of\n", { "type": "MathFragment", "mathLanguage": "mathml", "text": "E8", "meta": { "altText": "E_{8}" } }, "’s and hyperbolic forms\n", { "type": "MathFragment", "mathLanguage": "mathml", "text": "(0110)", "meta": { "altText": "(\\begin{smallmatrix}0&1\\\\\n1&0\\end{smallmatrix})" } }, "." ] }, { "type": "Paragraph", "id": "S2.SSx3.p6", "content": [ "Thus Rochlin’s theorem shows that half of the elements in the infinite set of even indefinite unimodular forms cannot\nappear as the intersection form of any smooth closed almost parallelizable four-manifold: namely, those with an odd\nnumber of ", { "type": "MathFragment", "mathLanguage": "mathml", "text": "E8", "meta": { "altText": "E_{8}" } }, "’s. An example that does appear is the ubiquitous K3 complex surface whose intersection form is two\n", { "type": "MathFragment", "mathLanguage": "mathml", "text": "E8", "meta": { "altText": "E_{8}" } }, "’s and three hyperbolic forms." ] }, { "type": "Paragraph", "id": "S2.SSx3.p7", "content": [ "This result set the stage for another important development in topology, geometry and analysis." ] }, { "type": "Paragraph", "id": "S2.SSx3.p8", "content": [ "This relates to definite forms." ] }, { "type": "Paragraph", "id": "S2.SSx3.p9", "content": [ "In number theory one also knows that there are finitely many unimodular definite symmetric forms of a given rank, the\nnumber growing exponentially with the rank." ] }, { "type": "Paragraph", "id": "S2.SSx3.p10", "content": [ { "type": "Emphasis", "content": [ "Donaldson" ] }, " proved that none of those definite forms except the identity form occurs as the intersection form of\na smooth four-manifold. This is the first theorem of the unexpected Donaldson theory discovered three decades after\nRochlin’s theorem." ] }, { "type": "Paragraph", "id": "S2.SSx3.p11", "content": [ { "type": "Emphasis", "content": [ "Freedman" ] }, " at the same time showed remarkably that every unimodular form occurs for closed topological\nfour-manifolds." ] }, { "type": "Paragraph", "id": "S2.SSx3.p12", "content": [ "Donaldson theory does not prove Rochlin’s theorem, because Rochlin’s statement involves hyperbolic forms." ] }, { "type": "Paragraph", "id": "S2.SSx3.p13", "content": [ "In fact, there is an intermediate class of manifolds between smooth and topological where the analysis of Donaldson\ntheory is perfectly valid." ] }, { "type": "Paragraph", "id": "S2.SSx3.p14", "content": [ "More precisely, there are two such intermediate classes of manifolds, the ones with coordinate charts where the\ntransition mappings are bi-Lipschitz, and the ones where the transition mappings are quasi-conformal." ] }, { "type": "Paragraph", "id": "S2.SSx3.p15", "content": [ "Let\nus call these ", { "type": "Emphasis", "content": [ "Sobolev " ] }, "manifolds." ] }, { "type": "Heading", "id": "S2.SSx4", "depth": 2, "content": [ "282*. Problem." ] }, { "type": "Paragraph", "id": "S2.SSx4.p1", "content": [ "Is Rochlin’s theorem true for these Sobolev four-manifolds?\n" ] }, { "type": "Heading", "id": "S2.SSx5", "depth": 2, "content": [ "283*. Conjecture." ] }, { "type": "Paragraph", "id": "S2.SSx5.p1", "content": [ "If Rochlin’s theorem is true for Sobolev four-manifolds,\nthen Sobolev four-manifolds are actually smoothable." ] }, { "type": "Heading", "id": "S2.SSx6", "depth": 2, "content": [ "Information" ] }, { "type": "Paragraph", "id": "S2.SSx6.p1", "content": [ "Closed topological four-manifolds are almost smoothable, namely, they are smoothable in the complement of a point (see\nsurveys and book by ", { "type": "Emphasis", "content": [ "Frank Quinn" ] }, ")." ] }, { "type": "Paragraph", "id": "S2.SSx6.p2", "content": [ "Also, except for dimension four, all topological manifolds carry unique Sobolev structures of each type." ] }, { "type": "Paragraph", "id": "S2.SSx6.p3", "content": [ "The proof makes heavy use of the ", { "type": "Emphasis", "content": [ "Kirby–Edwards" ] }, " completely elementary and very ingenious construction of\npaths of homeomorphisms between nearby homeomorphisms in all dimensions (late 1960s)." ] }, { "type": "Paragraph", "id": "S2.SSx6.p4", "content": [ "These paths of homeomorphisms allowed ", { "type": "Emphasis", "content": [ "Siebenmann" ] }, " in 1969 to construct higher-dimensional manifold\ncounterexamples to the Hauptvermutung soon after he understood the precise role played by Rochlin’s theorem about four\ndimensions in this question." ] }, { "type": "Heading", "id": "S2.SSx7", "depth": 2, "content": [ "Operators on Hilbert Space" ] }, { "type": "Paragraph", "id": "S2.SSx7.p1", "content": [ "The signature operator twisted by a vector bundle exists in the Sobolev context. The unbounded version exists in\nthe Lipschitz context. The bounded version, just using the phase of the operator (which contains\nall of the\ntopological information), exists in the quasi-conformal context. Stiefel–Whitney classes make sense in these settings,\nso the possibility of constructing Dirac operators also makes sense. This is unknown at present (more below)." ] }, { "type": "Heading", "id": "S2.SSx8", "depth": 2, "content": [ "Physics" ] }, { "type": "Paragraph", "id": "S2.SSx8.p1", "content": [ "Donaldson theory is part of a larger quantum field theory which has an effective version obtained by integrating out\ncertain variables." ] }, { "type": "Paragraph", "id": "S2.SSx8.p2", "content": [ "This effective version has expression in terms of Dirac operators which depend on the tangent bundle. One knows that\nRochlin’s theorem can be deduced in a context using Dirac operators, the Atiyah–Singer index theorem and\nquaternions (more below)." ] }, { "type": "Paragraph", "id": "S2.SSx8.p3", "content": [ "Physicists believe that Donaldson theory and its effective version ", { "type": "Emphasis", "content": [ "Seiberg–Witten" ] }, " theory are equivalent. From\nthe perspective of Sobolev manifolds, Rochlin’s theorem provides a challenge to and an opportunity for understanding\nbetter this belief." ] }, { "type": "Heading", "id": "S2.SSx9", "depth": 2, "content": [ "More history" ] }, { "type": "Paragraph", "id": "S2.SSx9.p1", "content": [ "In the middle 1960s this author, as a second year Princeton topology grad student, was following the evidently\npowerful constructive cobordism techniques of ", { "type": "Emphasis", "content": [ "Browder" ] }, " and ", { "type": "Emphasis", "content": [ "Novikov" ] }, " classifying smooth manifolds in a\n", { "type": "Emphasis", "content": [ "homotopy type (simply connected) with stable tangent vector bundle specified" ] }, " plus the covering space\nmethod of ", { "type": "Emphasis", "content": [ "Novikov" ] }, " for showing that the rational Pontryagin classes were homeomorphism invariants. The\nmotivation was to study firstly, ", { "type": "Emphasis", "content": [ "PL-manifolds in a given homotopy type" ] }, "\nwithout\nPL-stable\ntangent\nmicrobundle specified and secondly, to study ", { "type": "Emphasis", "content": [ "PL-manifolds in a given homeomorphism type" ] }, " without\nPL-stable\ntangent microbundle specified. These formulations, suggested by the influence of ", { "type": "Emphasis", "content": [ "Milnor" ] }, " and\n", { "type": "Emphasis", "content": [ "Steenrod" ] }, ", had completely calculable outcomes, whereas every other formulation did not have such completely\ncalculable outcomes (simply connected and dimension greater than four)." ] }, { "type": "Paragraph", "id": "S2.SSx9.p2", "content": [ "Given a homotopy equivalence ", { "type": "MathFragment", "mathLanguage": "mathml", "text": "f:L→M", "meta": { "altText": "f\\colon L\\to M" } }, " one could define in all dimensions numerical obstructions to ", { "type": "MathFragment", "mathLanguage": "mathml", "text": "f", "meta": { "altText": "f" } }, " being\nhomotopic to a PL-homeomorphism via differences of signatures of ", { "type": "MathFragment", "mathLanguage": "mathml", "text": "V", "meta": { "altText": "V" } }, " and ", { "type": "MathFragment", "mathLanguage": "mathml", "text": "f−1⁢V", "meta": { "altText": "f^{-1}V" } }, ", where ", { "type": "MathFragment", "mathLanguage": "mathml", "text": "V", "meta": { "altText": "V" } }, " is a manifold cycle\nin ", { "type": "MathFragment", "mathLanguage": "mathml", "text": "M", "meta": { "altText": "M" } }, " and ", { "type": "MathFragment", "mathLanguage": "mathml", "text": "f−1", "meta": { "altText": "f^{-1}" } }, " is its transverse preimage in ", { "type": "MathFragment", "mathLanguage": "mathml", "text": "L", "meta": { "altText": "L" } }, ". These differences were divisible by eight because ", { "type": "MathFragment", "mathLanguage": "mathml", "text": "f", "meta": { "altText": "f" } }, " is a\nhomotopy equivalence and so pulls back Stiefel–Whitney classes. There were also modulo ", { "type": "MathFragment", "mathLanguage": "mathml", "text": "n", "meta": { "altText": "n" } }, " versions of this\npicture where ", { "type": "MathFragment", "mathLanguage": "mathml", "text": "V", "meta": { "altText": "V" } }, " is a mod ", { "type": "MathFragment", "mathLanguage": "mathml", "text": "n", "meta": { "altText": "n" } }, " manifold cycle." ] }, { "type": "Paragraph", "id": "S2.SSx9.p3", "content": [ "The vanishing for a finite generating set of these characteristic invariants of ", { "type": "MathFragment", "mathLanguage": "mathml", "text": "f", "meta": { "altText": "f" } }, " was necessary for ", { "type": "MathFragment", "mathLanguage": "mathml", "text": "f", "meta": { "altText": "f" } }, " to be\nhomotopic to a homeomorphism, and further to be homotopic to a PL-homeomorphism if for the mod ", { "type": "MathFragment", "mathLanguage": "mathml", "text": "n", "meta": { "altText": "n" } }, "\ncharacteristic cycles of dimension four the division by 8 was upgraded to a division by 16 using Rochlin’s\ntheorem. In higher dimensions than four this vanishing and this refined vanishing were also respectively\nsufficient in the simply connected case." ] }, { "type": "Paragraph", "id": "S2.SSx9.p4", "content": [ "(This description for\nsimplicity has absorbed the mod two Arf–Kervaire invariants in dim ", { "type": "MathFragment", "mathLanguage": "mathml", "text": "4⁢k−2", "meta": { "altText": "4k-2" } }, "\n[first\nencountered for ", { "type": "MathFragment", "mathLanguage": "mathml", "text": "k=1", "meta": { "altText": "k=1" } }, " by Pontryagin in his misstep of 1942] into the mod two signature invariants in dimension ", { "type": "MathFragment", "mathLanguage": "mathml", "text": "4⁢k", "meta": { "altText": "4k" } }, " by\ncrossing them with ", { "type": "MathFragment", "mathLanguage": "mathml", "text": "ℝ⁢P2", "meta": { "altText": "{\\mathbb{R}}P^{2}" } }, ",\ndescribed in the work with ", { "type": "Emphasis", "content": [ "John Morgan" ] }, ", Annals of Math., 1974.)" ] }, { "type": "Paragraph", "id": "S2.SSx9.p5", "content": [ "The refined vanishing sufficiency was achieved in 1966 for the PL-homeomorphism case (“On the Hauptvermutung for Manifolds” Bulletin of the AMS, July 1967)\nand the vanishing sufficiency became valid for the homeomorphism case as a corollary\nin 1969 of the general topological manifold theory achieved by Kirby–Siebenmann." ] }, { "type": "Paragraph", "id": "S2.SSx9.p6", "content": [ "The Rochlin refinement by 16 rather than 8 gave an order-two class in the integral fourth cohomology of ", { "type": "MathFragment", "mathLanguage": "mathml", "text": "L", "meta": { "altText": "L" } }, "\ncanonically defined when ", { "type": "MathFragment", "mathLanguage": "mathml", "text": "f", "meta": { "altText": "f" } }, " is a homeomorphism. This heretofore unnamed class was dubbed the Rochlin class in the\nproceedings of the Rochlin\ncentenary\nconference in St. Petersburg a few years ago." ] }, { "type": "Paragraph", "id": "S2.SSx9.p7", "content": [ "In the hands of ", { "type": "Emphasis", "content": [ "Kirby" ] }, " and ", { "type": "Emphasis", "content": [ "Siebenmann" ] }, ", the entire difference between the\nPL- and topological manifold\ncategories in higher dimensions could be completely understood by the profound factor of two implied by Rochlin’s\n16. They proved in 1969 that the homeomorphism ", { "type": "MathFragment", "mathLanguage": "mathml", "text": "f", "meta": { "altText": "f" } }, " was connected by a path of homeomorphisms to a\nPL-homeomorphism\n(higher dimensions and no simply connected hypothesis required) if and only if a ", { "type": "Emphasis", "content": [ "“mod two Rochlin class”" ] }, " in the\ndegree three cohomology of ", { "type": "MathFragment", "mathLanguage": "mathml", "text": "L", "meta": { "altText": "L" } }, " with ", { "type": "MathFragment", "mathLanguage": "mathml", "text": "ℤ/2⁢ℤ", "meta": { "altText": "{\\mathbb{Z}}/2{\\mathbb{Z}}" } }, " coefficients vanished, and all of these classes,\nreferred to as Kirby–Siebenmann\nclasses, are realized by geometric examples." ] }, { "type": "Paragraph", "id": "S2.SSx9.p8", "content": [ "These two Rochlin classes, the mod two Rochlin type class in degree three of Kirby and Siebenmann obstructing an\nisotopy of the homeomorphism to a\nPL-homeomorphism and the integral Rochlin class of order two in degree four\nobstructing a homotopy of the homeomorphism to a PL-homeomorphism are related by the integral Bockstein operation.\nThe Bockstein operation takes an integral cochain representative of the mod two class and forms 1/2 of its coboundary\nto obtain an integral cocycle in degree four (so that two times it is obviously a coboundary)." ] }, { "type": "Paragraph", "id": "S2.SSx9.p9", "content": [ "This “Bockstein of the mod two Kirby–Siebenmann class is the order-two integral Rochlin class” discussion is related\nto the important recent discovery by ", { "type": "Emphasis", "content": [ "Manolescu" ] }, ", reported at the Rochlin Conference, of the existence of\nhigher-dimensional\ntopological manifolds not homeomorphic to a triangulated compact space." ] }, { "type": "Heading", "id": "S2.SSx10", "depth": 2, "content": [ "More information for the Rochlin problem and the Rochlin conjecture" ] }, { "type": "Paragraph", "id": "S2.SSx10.p1", "content": [ "Work of Kirby and Edwards (mentioned above) and work of Kirby depending on that of Novikov was used to show in 1976\nthat topological manifolds in all dimensions, except for dimension four, could be provided with unique Sobolev\nstructures of either type. This used a substitution of the ", { "type": "MathFragment", "mathLanguage": "mathml", "text": "d", "meta": { "altText": "d" } }, "-torus used in those works by an almost parallelizable\nclosed hyperbolic ", { "type": "MathFragment", "mathLanguage": "mathml", "text": "d", "meta": { "altText": "d" } }, "-manifold (D. S. “Hyperbolic Geometry and Homeomorphisms” in the book “Geometric Topology,” Academic Press, 1979).\n" ] }, { "type": "Paragraph", "id": "S2.SSx10.p2", "content": [ "Interestingly, the existence of these almost parallelizable hyperbolic manifolds depends on an argument learned from\nwork of ", { "type": "Emphasis", "content": [ "Deligne" ] }, " and ", { "type": "Emphasis", "content": [ "Mazur" ] }, " that the algebraic topology modulo ", { "type": "MathFragment", "mathLanguage": "mathml", "text": "n", "meta": { "altText": "n" } }, " of a complex algebraic variety\ncan be defined for the algebraic variety reduced mod ", { "type": "MathFragment", "mathLanguage": "mathml", "text": "p", "meta": { "altText": "p" } }, " for ", { "type": "MathFragment", "mathLanguage": "mathml", "text": "p", "meta": { "altText": "p" } }, " prime and not dividing ", { "type": "MathFragment", "mathLanguage": "mathml", "text": "n", "meta": { "altText": "n" } }, ", and not involved\nawkwardly in the defining equations of the variety." ] }, { "type": "Paragraph", "id": "S2.SSx10.p3", "content": [ "After the opposite results of Donaldson and Freedman in 1982 it was natural to ask about their results for the\nintermediate class of Sobolev four-manifolds. The answer was: Donaldson theory works for both classes of Sobolev\nfour-manifolds (S. Donaldson and D. S. “Quasiconformal 4-Manifolds,” Acta Mathematica, 1989).\n" ] }, { "type": "Paragraph", "id": "S2.SSx10.p4", "content": [ "In studying Rochlin’s theorem in the Sobolev context, it is useful to know that the index theorem holds\nthere (", { "type": "Emphasis", "content": [ "N. Teleman" ] }, ") and that there are local representatives for the Pontryagin classes defined using the\nbounded phase of the signature operator in ", { "type": "Emphasis", "content": [ "Alain Connes’" ] }, " perspective of non-commutative geometry (A. Connes, N. Teleman and D. S. “Quasiconformal Mappings, Operators on Hilbert Space and Local Formulae for Characteristic Classes,” Topology, 1994).\n" ] }, { "type": "Paragraph", "id": "S2.SSx10.p5", "content": [ "Considerations related to the construction of Dirac operators and the context of smooth versus Sobolev manifolds plus\na smoothability and a Dirac operator conjecture are discussed in D. S. “On the Foundation of Geometry, Analysis and the Differentiable Structure for Manifolds” in the book “Low Dimensional Topology,” World Scientific, 1999.\n" ] }, { "type": "Heading", "id": "S3", "depth": 1, "content": [ "III Solutions" ] }, { "type": "Heading", "id": "S3.SSx1", "depth": 2, "content": [ "269" ] }, { "type": "Paragraph", "content": [ "Consider two positive integers ", { "type": "MathFragment", "mathLanguage": "mathml", "text": "n≥1", "meta": { "altText": "n\\geq 1" } }, " and ", { "type": "MathFragment", "mathLanguage": "mathml", "text": "a≥2", "meta": { "altText": "a\\geq 2" } }, " such that" ] }, { "type": "MathBlock", "id": "S3.Ex2", "mathLanguage": "mathml", "text": "a2⁢n+an+1", "meta": { "altText": "a^{2n}+a^{n}+1" } }, { "type": "Paragraph", "content": [ "is a prime.\nProve that ", { "type": "MathFragment", "mathLanguage": "mathml", "text": "n", "meta": { "altText": "n" } }, " is a power of ", { "type": "MathFragment", "mathLanguage": "mathml", "text": "3", "meta": { "altText": "3" } }, "." ] }, { "type": "Paragraph", "id": "S3.SSx1.p2", "content": [ { "type": "Emphasis", "content": [ "Dorin Andrica and George Cătălin Ţurcaş (Babeş–Bolyai University, Cluj-Napoca, Romania)" ] } ] }, { "type": "Heading", "id": "S3.SSx1.SSSx1", "depth": 3, "content": [ "Proof by the proposers" ] }, { "type": "Paragraph", "content": [ { "type": "Emphasis", "content": [ "Proof 1." ] }, " Write" ] }, { "type": "MathBlock", "id": "S3.Ex3", "mathLanguage": "mathml", "text": "a2⁢n+an+1=a3⁢n−1an−1.", "meta": { "altText": "a^{2n}+a^{n}+1=\\frac{a^{3n}-1}{a^{n}-1}." } }, { "type": "Paragraph", "content": [ "If our number is a prime, then all factors of ", { "type": "MathFragment", "mathLanguage": "mathml", "text": "a3⁢n−1", "meta": { "altText": "a^{3n}-1" } }, " must be factors of ", { "type": "MathFragment", "mathLanguage": "mathml", "text": "an−1", "meta": { "altText": "a^{n}-1" } }, " and our number. Firstly, we will\nprove that ", { "type": "MathFragment", "mathLanguage": "mathml", "text": "3∣n", "meta": { "altText": "3\\mid n" } }, ". Suppose this is not true. Then ", { "type": "MathFragment", "mathLanguage": "mathml", "text": "a3⁢n−1", "meta": { "altText": "a^{3n}-1" } }, " is divisible by ", { "type": "MathFragment", "mathLanguage": "mathml", "text": "a3−1", "meta": { "altText": "a^{3}-1" } }, ", and from ", { "type": "MathFragment", "mathLanguage": "mathml", "text": "gcd⁡(3,n)=1", "meta": { "altText": "\\gcd(3,n)=1" } }, " it\nfollows that" ] }, { "type": "MathBlock", "id": "S3.Ex4", "mathLanguage": "mathml", "text": "gcd⁡(a3−1,an−1)=a−1,", "meta": { "altText": "\\gcd(a^{3}-1,a^{n}-1)=a-1," } }, { "type": "Paragraph", "content": [ "hence ", { "type": "MathFragment", "mathLanguage": "mathml", "text": "a3⁢n−1", "meta": { "altText": "a^{3n}-1" } }, " is divisible by ", { "type": "MathFragment", "mathLanguage": "mathml", "text": "B=a2+a+1", "meta": { "altText": "B=a^{2}+a+1" } }, ". Now we have ", { "type": "MathFragment", "mathLanguage": "mathml", "text": "gcd⁡(B,an−1)=1", "meta": { "altText": "\\gcd(B,\\allowbreak a^{n}-1)=1" } }, " and" ] }, { "type": "MathBlock", "id": "S3.Ex5", "mathLanguage": "mathml", "text": "gcd⁡(B,a2⁢n+an+1)=1", "meta": { "altText": "\\gcd(B,a^{2n}+a^{n}+1)=1" } }, { "type": "Paragraph", "content": [ "(because\n", { "type": "MathFragment", "mathLanguage": "mathml", "text": "a2⁢n+an+1", "meta": { "altText": "a^{2n}+a^{n}+1" } }, " is a prime). This is a contradiction, which implies that ", { "type": "MathFragment", "mathLanguage": "mathml", "text": "3∣n", "meta": { "altText": "3\\mid n" } }, "." ] }, { "type": "Paragraph", "content": [ "Assuming ", { "type": "MathFragment", "mathLanguage": "mathml", "text": "n=3⁢k", "meta": { "altText": "n=3k" } }, " and ", { "type": "MathFragment", "mathLanguage": "mathml", "text": "b=a3", "meta": { "altText": "b=a^{3}" } }, ", we have" ] }, { "type": "MathBlock", "id": "S3.Ex6", "mathLanguage": "mathml", "text": "a2⁢n+an+1=a6⁢k+a3⁢k+1=b2⁢k+b+1.", "meta": { "altText": "a^{2n}+a^{n}+1=a^{6k}+a^{3k}+1=b^{2k}+b+1." } }, { "type": "Paragraph", "content": [ "Using the above argument we obtain ", { "type": "MathFragment", "mathLanguage": "mathml", "text": "3∣k", "meta": { "altText": "3\\mid k" } }, ", and the conclusion follows." ] }, { "type": "Paragraph", "id": "S3.SSx1.SSSx1.p4", "content": [ { "type": "Emphasis", "content": [ "Proof 2." ] }, "\nWe start by presenting the following classical\nresult." ] }, { "type": "Claim", "id": "Thmlemma1", "claimType": "Lemma", "label": "Lemma 1.", "title": [ { "type": "Strong", "content": [ "Lemma 1" ] }, { "type": "Strong", "content": [ "." ] } ], "content": [ { "type": "Paragraph", "id": "Thmlemma1.p1", "content": [ { "type": "Emphasis", "content": [ "Let ", { "type": "MathFragment", "mathLanguage": "mathml", "text": "p≠3", "meta": { "altText": "p\\neq 3" } }, " be a prime. Then the polynomial\n", { "type": "MathFragment", "mathLanguage": "mathml", "text": "X2+X+1", "meta": { "altText": "X^{2}+X+1" } }, "\ndivides\n", { "type": "MathFragment", "mathLanguage": "mathml", "text": "X2⁢p+Xp+1", "meta": { "altText": "X^{2p}+X^{p}+1" } }, "\nin ", { "type": "MathFragment", "mathLanguage": "mathml", "text": "ℤ⁢[X]", "meta": { "altText": "\\mathbb{Z}[X]" } }, "." ] } ] } ] }, { "type": "Claim", "claimType": "Proof", "label": "Proof.", "title": [ "Proof." ], "content": [ { "type": "Paragraph", "content": [ "Let\n", { "type": "MathFragment", "mathLanguage": "mathml", "text": "ε", "meta": { "altText": "\\varepsilon" } }, " be a non-trivial third root of unity. Then, since ", { "type": "MathFragment", "mathLanguage": "mathml", "text": "p", "meta": { "altText": "p" } }, " and ", { "type": "MathFragment", "mathLanguage": "mathml", "text": "2⁢p", "meta": { "altText": "2p" } }, " have distinct residues modulo ", { "type": "MathFragment", "mathLanguage": "mathml", "text": "3", "meta": { "altText": "3" } }, ", it is readily seen that" ] }, { "type": "MathBlock", "id": "S3.Ex7", "mathLanguage": "mathml", "text": "ε2⁢p+εp+1=ε2+ε+1=0,", "meta": { "altText": "\\varepsilon^{2p}+\\varepsilon^{p}+1=\\varepsilon^{2}+\\varepsilon+1=0," } }, { "type": "Paragraph", "content": [ "so ", { "type": "MathFragment", "mathLanguage": "mathml", "text": "ε", "meta": { "altText": "\\varepsilon" } }, " is a root of ", { "type": "MathFragment", "mathLanguage": "mathml", "text": "X2⁢p+Xp+1", "meta": { "altText": "X^{2p}+X^{p}+1" } }, ". However, we know that ", { "type": "MathFragment", "mathLanguage": "mathml", "text": "X2+X+1", "meta": { "altText": "X^{2}+X+1" } }, " is the minimal (hence irreducible)\npolynomial of ", { "type": "MathFragment", "mathLanguage": "mathml", "text": "ε", "meta": { "altText": "\\varepsilon" } }, " over ", { "type": "MathFragment", "mathLanguage": "mathml", "text": "ℚ", "meta": { "altText": "\\mathbb{Q}" } }, ",\ntherefore" ] }, { "type": "MathBlock", "id": "S3.Ex8", "mathLanguage": "mathml", "text": "(X2+X+1)∣(X2⁢p+Xp+1)", "meta": { "altText": "(X^{2}+X+1)\\mid(X^{2p}+X^{p}+1)" } }, { "type": "Paragraph", "content": [ "in ", { "type": "MathFragment", "mathLanguage": "mathml", "text": "ℚ⁢[X]", "meta": { "altText": "\\mathbb{Q}[X]" } }, ". As the\npolynomials are monic with integer coefficients, it follows that the divisibility holds over ", { "type": "MathFragment", "mathLanguage": "mathml", "text": "ℤ⁢[X]", "meta": { "altText": "\\mathbb{Z}[X]" } }, ".\n∎" ] } ] }, { "type": "Paragraph", "content": [ "Returning to our problem, suppose that ", { "type": "MathFragment", "mathLanguage": "mathml", "text": "n", "meta": { "altText": "n" } }, " has a prime factor ", { "type": "MathFragment", "mathLanguage": "mathml", "text": "p≠3", "meta": { "altText": "p\\neq 3" } }, ". Write ", { "type": "MathFragment", "mathLanguage": "mathml", "text": "n=p⁢m", "meta": { "altText": "n=pm" } }, ". Then, by Lemma ", { "type": "Cite", "target": "Thmlemma1", "content": [ "1" ] }, "," ] }, { "type": "MathBlock", "id": "S3.Ex9", "mathLanguage": "mathml", "text": "(a2⁢m+am+1)∣(a2⁢n+an+1).", "meta": { "altText": "(a^{2m}+a^{m}+1)\\mid(a^{2n}+a^{n}+1)." } }, { "type": "Paragraph", "id": "S3.SSx1.SSSx1.p7", "content": [ "Since ", { "type": "MathFragment", "mathLanguage": "mathml", "text": "a≥2", "meta": { "altText": "a\\geq 2" } }, ", we have that ", { "type": "MathFragment", "mathLanguage": "mathml", "text": "1<a2⁢m+am+1<a2⁢n+an+1", "meta": { "altText": "1a2⁢n+an+1", "meta": { "altText": "a^{2n}+a^{n}+1" } }, " is not prime." ] }, { "type": "Paragraph", "id": "S3.SSx1.SSSx1.p8", "content": [ "We proved that if ", { "type": "MathFragment", "mathLanguage": "mathml", "text": "a2⁢n+an+1", "meta": { "altText": "a^{2n}+a^{n}+1" } }, " is prime, then ", { "type": "MathFragment", "mathLanguage": "mathml", "text": "n=3k", "meta": { "altText": "n=3^{k}" } }, "." ] }, { "type": "Paragraph", "id": "S3.SSx1.SSSx1.p10", "content": [ { "type": "Emphasis", "content": [ "Remark." ] }, " A few computational experiments with MAGMA suggest the following conjecture:" ] }, { "type": "Paragraph", "id": "S3.SSx1.SSSx1.p12", "content": [ { "type": "Emphasis", "content": [ "Conjecture." ] }, { "type": "Emphasis", "content": [ "For every positive integer ", { "type": "MathFragment", "mathLanguage": "mathml", "text": "a≥2", "meta": { "altText": "a\\geq 2" } }, " the numbers ", { "type": "MathFragment", "mathLanguage": "mathml", "text": "a2⋅3n+a3n+1", "meta": { "altText": "a^{2\\cdot 3^{n}}+a^{3^{n}}+1" } }, ", ", { "type": "MathFragment", "mathLanguage": "mathml", "text": "n=0,1,…", "meta": { "altText": "n=0,1,\\ldots" } }, ", are square-free." ] } ] }, { "type": "Paragraph", "content": [ "(i) The value ", { "type": "MathFragment", "mathLanguage": "mathml", "text": "a=2", "meta": { "altText": "a=2" } }, " gives rise to the sequence ", { "type": "MathFragment", "mathLanguage": "mathml", "text": "Dn=43n+23n+1", "meta": { "altText": "D_{n}=4^{3^{n}}+2^{3^{n}}+1" } }, ", ", { "type": "MathFragment", "mathLanguage": "mathml", "text": "n=0,1,2,…", "meta": { "altText": "n=0,1,2,\\ldots" } }, ".\nWe have:" ] }, { "type": "Paragraph", "content": [] }, { "type": "List", "items": [ { "type": "ListItem", "content": [ { "type": "Paragraph", "id": "S3.I1.i1.p1", "content": [ { "type": "MathFragment", "mathLanguage": "mathml", "text": "D0=4+2+1=7", "meta": { "altText": "D_{0}=4+2+1=7" } }, ", is a prime;" ] } ] }, { "type": "ListItem", "content": [ { "type": "Paragraph", "id": "S3.I1.i2.p1", "content": [ { "type": "MathFragment", "mathLanguage": "mathml", "text": "D1=43+23+1=73", "meta": { "altText": "D_{1}=4^{3}+2^{3}+1=73" } }, ", is a prime;" ] } ] }, { "type": "ListItem", "content": [ { "type": "Paragraph", "id": "S3.I1.i3.p1", "content": [ { "type": "MathFragment", "mathLanguage": "mathml", "text": "D2=432+232+1=262657", "meta": { "altText": "D_{2}=4^{3^{2}}+2^{3^{2}}+1=262657" } }, ", is a prime;" ] } ] }, { "type": "ListItem", "content": [ { "type": "Paragraph", "id": "S3.I1.i4.p1", "content": [ { "type": "MathFragment", "mathLanguage": "mathml", "text": "D3=433+233+1=18014398643699713=2593×71119×97685839", "meta": { "altText": "D_{3}=4^{3^{3}}+2^{3^{3}}+1=18014398643699713=2593\\times 71119\\allowbreak{}\\times 97685839" } }, ", it has three distinct prime factors;" ] } ] }, { "type": "ListItem", "content": [ { "type": "Paragraph", "id": "S3.I1.i5.p1", "content": [ { "type": "MathFragment", "mathLanguage": "mathml", "text": "D4=434+234+1", "meta": { "altText": "D_{4}=4^{3^{4}}+2^{3^{4}}+1" } }, " is square-free, it has ", { "type": "MathFragment", "mathLanguage": "mathml", "text": "16", "meta": { "altText": "16" } }, " distinct prime factors, the smallest being ", { "type": "MathFragment", "mathLanguage": "mathml", "text": "487", "meta": { "altText": "487" } }, ";" ] } ] }, { "type": "ListItem", "content": [ { "type": "Paragraph", "id": "S3.I1.i6.p1", "content": [ { "type": "MathFragment", "mathLanguage": "mathml", "text": "D5", "meta": { "altText": "D_{5}" } }, " is square-free, but not prime;" ] } ] }, { "type": "ListItem", "content": [ { "type": "Paragraph", "id": "S3.I1.i7.p1", "content": [ { "type": "MathFragment", "mathLanguage": "mathml", "text": "D6", "meta": { "altText": "D_{6}" } }, ", ", { "type": "MathFragment", "mathLanguage": "mathml", "text": "D7", "meta": { "altText": "D_{7}" } }, ", ", { "type": "MathFragment", "mathLanguage": "mathml", "text": "D8", "meta": { "altText": "D_{8}" } }, ", ", { "type": "MathFragment", "mathLanguage": "mathml", "text": "D9", "meta": { "altText": "D_{9}" } }, " and ", { "type": "MathFragment", "mathLanguage": "mathml", "text": "D10", "meta": { "altText": "D_{10}" } }, " are not primes, but we\ndo not know if they are square\nfree." ] } ] } ], "order": "Ascending", "meta": { "listType": "order" } }, { "type": "Paragraph", "content": [ "(ii) The value ", { "type": "MathFragment", "mathLanguage": "mathml", "text": "a=3", "meta": { "altText": "a=3" } }, " gives rise to the sequence ", { "type": "MathFragment", "mathLanguage": "mathml", "text": "En=93n+33n+1", "meta": { "altText": "E_{n}=9^{3^{n}}+3^{3^{n}}+1" } }, ", ", { "type": "MathFragment", "mathLanguage": "mathml", "text": "n=0,1,2,…", "meta": { "altText": "n=0,1,2,\\ldots" } }, ".\nWe have:" ] }, { "type": "Paragraph", "content": [] }, { "type": "List", "items": [ { "type": "ListItem", "content": [ { "type": "Paragraph", "id": "S3.I2.i1.p1", "content": [ { "type": "MathFragment", "mathLanguage": "mathml", "text": "E0", "meta": { "altText": "E_{0}" } }, " and ", { "type": "MathFragment", "mathLanguage": "mathml", "text": "E1", "meta": { "altText": "E_{1}" } }, " are primes;" ] } ] }, { "type": "ListItem", "content": [ { "type": "Paragraph", "id": "S3.I2.i2.p1", "content": [ { "type": "MathFragment", "mathLanguage": "mathml", "text": "E2=109×433×8209", "meta": { "altText": "E_{2}=109\\times 433\\times 8209" } }, ";" ] } ] }, { "type": "ListItem", "content": [ { "type": "Paragraph", "id": "S3.I2.i3.p1", "content": [ { "type": "MathFragment", "mathLanguage": "mathml", "text": "E3=3889×1190701×12557612956332313", "meta": { "altText": "E_{3}=3889\\times 1190701\\times 12557612956332313" } }, ";" ] } ] }, { "type": "ListItem", "content": [ { "type": "Paragraph", "id": "S3.I2.i4.p1", "content": [ { "type": "MathFragment", "mathLanguage": "mathml", "text": "E4=70957×6627097", "meta": { "altText": "E_{4}=70957\\times 6627097" } }, { "type": "MathFragment", "mathLanguage": "mathml", "text": "×21835473162448454819220238921", "meta": { "altText": "{}\\times 21835473162448454819220238921" } }, { "type": "MathFragment", "mathLanguage": "mathml", "text": "×19149704835029612299033896988868835457", "meta": { "altText": "{}\\times 19149704835029612299033896988868835457" } }, ";" ] } ] }, { "type": "ListItem", "content": [ { "type": "Paragraph", "id": "S3.I2.i5.p1", "content": [ { "type": "MathFragment", "mathLanguage": "mathml", "text": "E5", "meta": { "altText": "E_{5}" } }, " is square-free, but not prime;" ] } ] }, { "type": "ListItem", "content": [ { "type": "Paragraph", "id": "S3.I2.i6.p1", "content": [ { "type": "MathFragment", "mathLanguage": "mathml", "text": "E6", "meta": { "altText": "E_{6}" } }, ", ", { "type": "MathFragment", "mathLanguage": "mathml", "text": "E7", "meta": { "altText": "E_{7}" } }, ", ", { "type": "MathFragment", "mathLanguage": "mathml", "text": "E8", "meta": { "altText": "E_{8}" } }, ", ", { "type": "MathFragment", "mathLanguage": "mathml", "text": "E9", "meta": { "altText": "E_{9}" } }, ", ", { "type": "MathFragment", "mathLanguage": "mathml", "text": "E10", "meta": { "altText": "E_{10}" } }, " are not primes, but we\ndo not know if they are\nsquare-free." ] } ] } ], "order": "Ascending", "meta": { "listType": "order" } }, { "type": "Heading", "id": "S3.SSx2", "depth": 2, "content": [ "270" ] }, { "type": "Paragraph", "content": [ "The Collatz map is defined as follows:" ] }, { "type": "MathBlock", "id": "S3.Ex10", "mathLanguage": "mathml", "text": "Col⁡(n)⁢≔⁢{n/2if⁢n⁢is even,3⁢n+1if⁢n⁢is odd.", "meta": { "altText": "\\operatorname{Col}(n)≔\\begin{cases}n/2&\\textrm{if}\\ n\\ \\textrm{is even},\\\\\n3n+1&\\textrm{if}\\ n\\ \\textrm{is odd}.\\end{cases}" } }, { "type": "Paragraph", "content": [ "Let\n" ] }, { "type": "MathBlock", "id": "S3.Ex11", "mathLanguage": "mathml", "text": "0:\\operatorname{Col}^{m}(n)\\geq x).\" display=\"block\">tm,x⁢≔⁢min⁡(n>0:Colm⁡(n)≥x).", "meta": { "altText": "t_{m,x}≔\\min(n>0:\\operatorname{Col}^{m}(n)\\geq x)." } }, { "type": "Paragraph", "content": [ "That is, ", { "type": "MathFragment", "mathLanguage": "mathml", "text": "tm,x", "meta": { "altText": "t_{m,x}" } }, " is the smallest integer such that, if we apply the Collatz map ", { "type": "MathFragment", "mathLanguage": "mathml", "text": "m", "meta": { "altText": "m" } }, " times, the result is larger\nthan ", { "type": "MathFragment", "mathLanguage": "mathml", "text": "x", "meta": { "altText": "x" } }, "." ] }, { "type": "Paragraph", "id": "S3.SSx2.p2", "content": [ "(a) Find ", { "type": "MathFragment", "mathLanguage": "mathml", "text": "t3,1000", "meta": { "altText": "t_{3,1000}" } }, " and ", { "type": "MathFragment", "mathLanguage": "mathml", "text": "t4,1000", "meta": { "altText": "t_{4,1000}" } }, "." ] }, { "type": "Paragraph", "content": [ "(b) Show that, for ", { "type": "MathFragment", "mathLanguage": "mathml", "text": "x", "meta": { "altText": "x" } }, " large enough (larger than (say) ", { "type": "MathFragment", "mathLanguage": "mathml", "text": "1000", "meta": { "altText": "1000" } }, "), we have" ] }, { "type": "MathBlock", "id": "S3.Ex12", "mathLanguage": "mathml", "text": "t4,x≡3mod4ort4,x≡6mod8.", "meta": { "altText": "t_{4,x}\\equiv 3\\bmod 4\\quad\\textrm{or}\\quad t_{4,x}\\equiv 6\\bmod 8." } }, { "type": "Paragraph", "id": "S3.SSx2.p4", "content": [ "(c) In general, for ", { "type": "MathFragment", "mathLanguage": "mathml", "text": "m", "meta": { "altText": "m" } }, " odd and ", { "type": "MathFragment", "mathLanguage": "mathml", "text": "x", "meta": { "altText": "x" } }, " large enough, there exists a constant ", { "type": "MathFragment", "mathLanguage": "mathml", "text": "Xm,x", "meta": { "altText": "X_{m,x}" } }, " such that ", { "type": "MathFragment", "mathLanguage": "mathml", "text": "tm,x", "meta": { "altText": "t_{m,x}" } }, " is\nthe smallest ", { "type": "MathFragment", "mathLanguage": "mathml", "text": "X_{m,x}\" display=\"inline\">n>Xm,x", "meta": { "altText": "n>X_{m,x}" } }, " such that ", { "type": "MathFragment", "mathLanguage": "mathml", "text": "n≡cmmodMm", "meta": { "altText": "n\\equiv c_{m}\\bmod M_{m}" } }, ".\nFind ", { "type": "MathFragment", "mathLanguage": "mathml", "text": "Mm", "meta": { "altText": "M_{m}" } }, " and relate ", { "type": "MathFragment", "mathLanguage": "mathml", "text": "cm", "meta": { "altText": "c_{m}" } }, " to ", { "type": "MathFragment", "mathLanguage": "mathml", "text": "cm−1", "meta": { "altText": "c_{m-1}" } }, "." ] }, { "type": "Paragraph", "id": "S3.SSx2.p5", "content": [ { "type": "Emphasis", "content": [ "Christopher Lutsko (Department of Mathematics, Rutgers University, Piscataway, USA)" ] } ] }, { "type": "Heading", "id": "S3.SSx2.SSSx1", "depth": 3, "content": [ "Solution by the proposer" ] }, { "type": "Paragraph", "content": [ "(a) Note that, if ", { "type": "MathFragment", "mathLanguage": "mathml", "text": "n", "meta": { "altText": "n" } }, " is odd, then ", { "type": "MathFragment", "mathLanguage": "mathml", "text": "3⁢n+1", "meta": { "altText": "3n+1" } }, " is necessarily even. Thus, after applying ", { "type": "MathFragment", "mathLanguage": "mathml", "text": "3⁢n+1", "meta": { "altText": "3n+1" } }, " we need to apply ", { "type": "MathFragment", "mathLanguage": "mathml", "text": "n/2", "meta": { "altText": "n/2" } }, ".\nTherefore, the map ", { "type": "MathFragment", "mathLanguage": "mathml", "text": "Col2⁡(n)", "meta": { "altText": "\\operatorname{Col}^{2}(n)" } }, " is bounded by ", { "type": "MathFragment", "mathLanguage": "mathml", "text": "3⁢n/2+1/2", "meta": { "altText": "3n/2+1/2" } }, ". Similarly, ", { "type": "MathFragment", "mathLanguage": "mathml", "text": "Col3⁡(n)", "meta": { "altText": "\\operatorname{Col}^{3}(n)" } }, " is upper\nbounded by approximately ", { "type": "MathFragment", "mathLanguage": "mathml", "text": "9⁢n/2+5/2", "meta": { "altText": "9n/2+5/2" } }, ". Thus," ] }, { "type": "MathBlock", "id": "S3.Ex13", "mathLanguage": "mathml", "text": "2000/9-5/9>221.\" display=\"block\">n>2000/9−5/9>221.", "meta": { "altText": "n>2000/9-5/9>221." } }, { "type": "Paragraph", "content": [ "Moreover, for ", { "type": "MathFragment", "mathLanguage": "mathml", "text": "Col3⁡(n)", "meta": { "altText": "\\operatorname{Col}^{3}(n)" } }, " to be as large as possible, both ", { "type": "MathFragment", "mathLanguage": "mathml", "text": "n", "meta": { "altText": "n" } }, " and ", { "type": "MathFragment", "mathLanguage": "mathml", "text": "Col2⁡(n)", "meta": { "altText": "\\operatorname{Col}^{2}(n)" } }, " must be\nodd. Therefore, we want ", { "type": "MathFragment", "mathLanguage": "mathml", "text": "n", "meta": { "altText": "n" } }, " odd and" ] }, { "type": "MathBlock", "id": "S3.Ex14", "mathLanguage": "mathml", "text": "3⁢n+1≡2mod4", "meta": { "altText": "3n+1\\equiv 2\\bmod{4}" } }, { "type": "Paragraph", "content": [ "or, equivalently,\n" ] }, { "type": "MathBlock", "id": "S3.Ex15", "mathLanguage": "mathml", "text": "n≡3mod4.", "meta": { "altText": "n\\equiv 3\\bmod{4}." } }, { "type": "Paragraph", "content": [ "The smallest ", { "type": "MathFragment", "mathLanguage": "mathml", "text": "n", "meta": { "altText": "n" } }, " larger than ", { "type": "MathFragment", "mathLanguage": "mathml", "text": "221", "meta": { "altText": "221" } }, " which is congruent to ", { "type": "MathFragment", "mathLanguage": "mathml", "text": "3mod4", "meta": { "altText": "3\\bmod{4}" } }, " is ", { "type": "MathFragment", "mathLanguage": "mathml", "text": "223", "meta": { "altText": "223" } }, "." ] }, { "type": "Paragraph", "content": [ "Similarly, ", { "type": "MathFragment", "mathLanguage": "mathml", "text": "Col4⁡(n)", "meta": { "altText": "\\operatorname{Col}^{4}(n)" } }, " is bounded by ", { "type": "MathFragment", "mathLanguage": "mathml", "text": "9⁢n/4+5/4", "meta": { "altText": "9n/4+5/4" } }, ".\nThus" ] }, { "type": "MathBlock", "id": "S3.Ex16", "mathLanguage": "mathml", "text": "4000/9-5/9>443.\" display=\"block\">n>4000/9−5/9>443.", "meta": { "altText": "n>4000/9-5/9>443." } }, { "type": "Paragraph", "content": [ "Moreover, to ensure we apply the map ", { "type": "MathFragment", "mathLanguage": "mathml", "text": "x↦3⁢x+1", "meta": { "altText": "x\\mapsto 3x+1" } }, " twice, there are two possibilities: If ", { "type": "MathFragment", "mathLanguage": "mathml", "text": "n", "meta": { "altText": "n" } }, " is odd, then we want" ] }, { "type": "MathBlock", "id": "S3.Ex17", "mathLanguage": "mathml", "text": "3⁢n+1≡2mod4,", "meta": { "altText": "3n+1\\equiv 2\\bmod{4}," } }, { "type": "Paragraph", "content": [ "which implies" ] }, { "type": "MathBlock", "id": "S3.Ex18", "mathLanguage": "mathml", "text": "n≡3mod4.", "meta": { "altText": "n\\equiv 3\\bmod{4}." } }, { "type": "Paragraph", "content": [ "If ", { "type": "MathFragment", "mathLanguage": "mathml", "text": "n", "meta": { "altText": "n" } }, " is even, then we want" ] }, { "type": "MathBlock", "id": "S3.Ex19", "mathLanguage": "mathml", "text": "3⁢n/2+1≡2mod4,", "meta": { "altText": "3n/2+1\\equiv 2\\bmod{4}," } }, { "type": "Paragraph", "content": [ "which is equivalent to" ] }, { "type": "MathBlock", "id": "S3.Ex20", "mathLanguage": "mathml", "text": "n≡6mod8.", "meta": { "altText": "n\\equiv 6\\bmod{8}." } }, { "type": "Paragraph", "content": [ "The smallest such number is ", { "type": "MathFragment", "mathLanguage": "mathml", "text": "446", "meta": { "altText": "446" } }, "." ] }, { "type": "Paragraph", "content": [ "(b) The general formula follows from the same line of reasoning." ] }, { "type": "Paragraph", "content": [ "(c)\nThe\nvalues ", { "type": "MathFragment", "mathLanguage": "mathml", "text": "Xm,x", "meta": { "altText": "X_{m,x}" } }, " can be slightly tricky, because of the ", { "type": "MathFragment", "mathLanguage": "mathml", "text": "+1", "meta": { "altText": "+1" } }, " in the definition of the Collatz map; in general," ] }, { "type": "MathBlock", "id": "S3.Ex21", "mathLanguage": "mathml", "text": "Xm,x=⌊2m−1/2⁢x3m+1/2⌋orXm,x=⌊2m−1/2⁢x3m+1/2⌋+1.", "meta": { "altText": "X_{m,x}= \\Bigl\\lfloor \\frac{2^{{m-1}/{2}}x}{3^{{m+1}/{2}}} \\Bigr\\rfloor \\quad\\textrm{or}\\quad{X_{m,x}={}} \\Bigl\\lfloor \\frac{2^{{m-1}/{2}}x}{3^{{m+1}/{2}}} \\Bigr\\rfloor +1." } }, { "type": "Paragraph", "id": "S3.SSx2.SSSx1.p5", "content": [ "For ", { "type": "MathFragment", "mathLanguage": "mathml", "text": "m=5", "meta": { "altText": "m=5" } }, ", the same line of reasoning yields ", { "type": "MathFragment", "mathLanguage": "mathml", "text": "n≡7mod8", "meta": { "altText": "n\\equiv 7\\bmod{8}" } }, "; for ", { "type": "MathFragment", "mathLanguage": "mathml", "text": "m=7", "meta": { "altText": "m=7" } }, " the solution requires\n", { "type": "MathFragment", "mathLanguage": "mathml", "text": "n≡3¯⁢(2⋅7−1)mod16", "meta": { "altText": "n\\equiv\\mkern 2.0mu\\overline{\\mkern-2.0mu3\\mkern-2.0mu}\\mkern 2.0mu(2\\cdot 7-1)\\bmod{16}" } }, ", where ", { "type": "MathFragment", "mathLanguage": "mathml", "text": "3¯", "meta": { "altText": "\\mkern 2.0mu\\overline{\\mkern-2.0mu3\\mkern-2.0mu}\\mkern 2.0mu" } }, " is the inverse of ", { "type": "MathFragment", "mathLanguage": "mathml", "text": "3", "meta": { "altText": "3" } }, " modulo ", { "type": "MathFragment", "mathLanguage": "mathml", "text": "16", "meta": { "altText": "16" } }, " (i.e., ", { "type": "MathFragment", "mathLanguage": "mathml", "text": "11", "meta": { "altText": "11" } }, ")." ] }, { "type": "Paragraph", "content": [ "In general, for ", { "type": "MathFragment", "mathLanguage": "mathml", "text": "m", "meta": { "altText": "m" } }, " odd, we have ", { "type": "MathFragment", "mathLanguage": "mathml", "text": "Mm=2m+1/2", "meta": { "altText": "M_{m}={2^{{m+1}/{2}}}" } }, " and" ] }, { "type": "MathBlock", "id": "S3.Ex22", "mathLanguage": "mathml", "text": "cm≡3¯⁢(2⁢cm−1−1)modMm,", "meta": { "altText": "c_{m}\\equiv\\mkern 2.0mu\\overline{\\mkern-2.0mu3\\mkern-2.0mu}\\mkern 2.0mu(2c_{m-1}-1)\\bmod{M_{m}}," } }, { "type": "Paragraph", "content": [ "where ", { "type": "MathFragment", "mathLanguage": "mathml", "text": "3¯", "meta": { "altText": "\\mkern 2.0mu\\overline{\\mkern-2.0mu3\\mkern-2.0mu}\\mkern 2.0mu" } }, " is the inverse of ", { "type": "MathFragment", "mathLanguage": "mathml", "text": "3", "meta": { "altText": "3" } }, " modulo ", { "type": "MathFragment", "mathLanguage": "mathml", "text": "Mm", "meta": { "altText": "M_{m}" } }, "." ] }, { "type": "Paragraph", "id": "S3.SSx2.SSSx1.p7", "content": [ "A similar expression can be derived for ", { "type": "MathFragment", "mathLanguage": "mathml", "text": "m", "meta": { "altText": "m" } }, " even, however, it is more complicated since ", { "type": "MathFragment", "mathLanguage": "mathml", "text": "n", "meta": { "altText": "n" } }, " could be either even or odd. ∎" ] }, { "type": "Heading", "id": "S3.SSx3", "depth": 2, "content": [ "271" ] }, { "type": "Paragraph", "id": "S3.SSx3.p1", "content": [ "The light-bulb problem: Alice and Bob are in jail for trying to divide by ", { "type": "MathFragment", "mathLanguage": "mathml", "text": "0", "meta": { "altText": "0" } }, ".\nThe jailer proposes the following game to decide their freedom: Alice will be shown an ", { "type": "MathFragment", "mathLanguage": "mathml", "text": "n×n", "meta": { "altText": "n\\times n" } }, " grid of light bulbs.\nThe jailer will point to a light bulb of his choice and Alice will decide whether it should be on or off.\nThen the jailer will point to another bulb of his choice and Alice will decide on/off.\nThis continues until the very last bulb, when the jailer will decide whether this bulb is on or off.\nSo the jailer controls the order of the selection, and the state of the final bulb.\nAlice is now removed from the room, and Bob is brought in.\nBob’s goal is to choose ", { "type": "MathFragment", "mathLanguage": "mathml", "text": "n", "meta": { "altText": "n" } }, " bulbs such that his selection includes the final bulb (the one determined by the jailer)." ] }, { "type": "Paragraph", "id": "S3.SSx3.p2", "content": [ "Is there a strategy that Alice and Bob can use to guarantee success?\nWhat if Bob does not know the orientation in which Alice saw the board (i.e., what if Bob does not know which are the rows and which are the columns)?" ] }, { "type": "Paragraph", "id": "S3.SSx3.p3", "content": [ { "type": "Emphasis", "content": [ "Christopher Lutsko (Department of Mathematics, Rutgers University, Piscataway, USA)" ] } ] }, { "type": "Heading", "id": "S3.SSx3.SSSx1", "depth": 3, "content": [ "Solution by the proposer" ] }, { "type": "Paragraph", "id": "S3.SSx3.SSSx1.p1", "content": [ "The strategy is as follows: Alice will choose ‘off’ for each light bulb in a row, until the last bulb in each row which\nshe will choose to be ‘on.’ Now if the jailer chooses the final bulb to be ‘off,’ then that row will be the only row\nwith only ‘off’ light bulbs. If the jailer chooses that the final bulb should be ‘on,’ then there will be ", { "type": "MathFragment", "mathLanguage": "mathml", "text": "n", "meta": { "altText": "n" } }, " ‘on’\nlight bulbs. Therefore, Bob’s strategy is, if there is a row which is entirely ‘off,’ then he chooses that row as his\n", { "type": "MathFragment", "mathLanguage": "mathml", "text": "n", "meta": { "altText": "n" } }, " choices. If each row has one ‘on’ light bulb, then he chooses all ‘on’ light bulbs." ] }, { "type": "Paragraph", "id": "S3.SSx3.SSSx1.p2", "content": [ "That strategy works because we have partitioned the ", { "type": "MathFragment", "mathLanguage": "mathml", "text": "n×n", "meta": { "altText": "n\\times n" } }, " grid into ", { "type": "MathFragment", "mathLanguage": "mathml", "text": "n", "meta": { "altText": "n" } }, " rows of size ", { "type": "MathFragment", "mathLanguage": "mathml", "text": "n", "meta": { "altText": "n" } }, ". If Bob does not know\nthe orientation of the board when Alice completed it, then the problem is trickier." ] }, { "type": "Paragraph", "id": "S3.SSx3.SSSx1.p3", "content": [ "If ", { "type": "MathFragment", "mathLanguage": "mathml", "text": "n=2", "meta": { "altText": "n=2" } }, ", the same strategy works with the diagonals instead of the rows (since the diagonals are rotationally\ninvariant). If ", { "type": "MathFragment", "mathLanguage": "mathml", "text": "n=m2", "meta": { "altText": "n=m^{2}" } }, ", then the same strategy works, since we can divide the board into ", { "type": "MathFragment", "mathLanguage": "mathml", "text": "n", "meta": { "altText": "n" } }, " squares of size\n", { "type": "MathFragment", "mathLanguage": "mathml", "text": "m×m", "meta": { "altText": "m\\times m" } }, "s, and use those instead of the rows. If ", { "type": "MathFragment", "mathLanguage": "mathml", "text": "n≠m2", "meta": { "altText": "n\\neq m^{2}" } }, ", I do not have a rotationally invariant solution.\nI conjecture that there is no winning strategy. ∎" ] }, { "type": "Heading", "id": "S3.SSx4", "depth": 2, "content": [ "272" ] }, { "type": "Paragraph", "id": "S3.SSx4.p1", "content": [ "Let ", { "type": "MathFragment", "mathLanguage": "mathml", "text": "p", "meta": { "altText": "p" } }, " and ", { "type": "MathFragment", "mathLanguage": "mathml", "text": "q", "meta": { "altText": "q" } }, " be coprime integers greater than or equal to ", { "type": "MathFragment", "mathLanguage": "mathml", "text": "2", "meta": { "altText": "2" } }, ".\nLet ", { "type": "MathFragment", "mathLanguage": "mathml", "text": "invq⁡(p)", "meta": { "altText": "\\operatorname{inv}_{q}(p)" } }, " and ", { "type": "MathFragment", "mathLanguage": "mathml", "text": "invp⁡(q)", "meta": { "altText": "\\operatorname{inv}_{p}(q)" } }, " denote the modular inverse of ", { "type": "MathFragment", "mathLanguage": "mathml", "text": "pmodq", "meta": { "altText": "p\\bmod q" } }, " and ", { "type": "MathFragment", "mathLanguage": "mathml", "text": "qmodp", "meta": { "altText": "q\\bmod p" } }, ", respectively.\nThat is, ", { "type": "MathFragment", "mathLanguage": "mathml", "text": "invq⁡(p)⁢p≡1modq", "meta": { "altText": "\\operatorname{inv}_{q}(p)p\\equiv 1\\bmod q" } }, " and ", { "type": "MathFragment", "mathLanguage": "mathml", "text": "invp⁡(q)⁢q≡1modp", "meta": { "altText": "\\operatorname{inv}_{p}(q)q\\equiv\\nobreak 1\\bmod p" } }, ".\n" ] }, { "type": "Paragraph", "content": [ "(a)\nShow that" ] }, { "type": "MathBlock", "id": "S3.Ex23", "mathLanguage": "mathml", "text": "\\frac{q}{2}.\" display=\"block\">invp⁡(q)≤p2if and only ifinvq⁡(p)>q2.", "meta": { "altText": "\\operatorname{inv}_{p}(q)\\leq\\frac{p}{2}\\quad\\textrm{if and only if}\\quad\\operatorname{inv}_{q}(p)>\\frac{q}{2}." } }, { "type": "Paragraph", "content": [ "(b)\nShow by providing an example that, if ", { "type": "MathFragment", "mathLanguage": "mathml", "text": "1≤u<v", "meta": { "altText": "1\\leq uα⁢≔⁢u/v", "meta": { "altText": "\\alpha≔u/v" } }, ", then the statement" ] }, { "type": "MathBlock", "id": "S3.E1", "label": "(1)", "mathLanguage": "mathml", "text": "(1-\\alpha)q\" display=\"block\">invp⁡(q)≤α⁢p if and only if invq⁡(p)>(1−α)⁢q", "meta": { "altText": "\\operatorname{inv}_{p}(q)\\leq\\alpha p\\quad\\textrm{ if and only if }\\quad\\operatorname{inv}_{q}(p)>(1-\\alpha)q" } }, { "type": "Paragraph", "content": [ "is not necessarily true." ] }, { "type": "Paragraph", "id": "S3.SSx4.p4", "content": [ "(c)\nWhat additional assumption should ", { "type": "MathFragment", "mathLanguage": "mathml", "text": "p", "meta": { "altText": "p" } }, " and/or ", { "type": "MathFragment", "mathLanguage": "mathml", "text": "q", "meta": { "altText": "q" } }, " satisfy so that the equivalence (", { "type": "Cite", "target": "S3-E1", "content": [ "1" ] }, ") holds?" ] }, { "type": "Paragraph", "id": "S3.SSx4.p5", "content": [ { "type": "Emphasis", "content": [ "Athanasios Sourmelidis (Institut für Analysis und Zahlentheorie, Technische Universität Graz, Austria)" ] } ] }, { "type": "Heading", "id": "S3.SSx4.SSSx1", "depth": 3, "content": [ "Solution by the proposer" ] }, { "type": "Paragraph", "content": [ "(a)\nBy coprimality, there are integers ", { "type": "MathFragment", "mathLanguage": "mathml", "text": "a", "meta": { "altText": "a" } }, " and ", { "type": "MathFragment", "mathLanguage": "mathml", "text": "b", "meta": { "altText": "b" } }, " such that ", { "type": "MathFragment", "mathLanguage": "mathml", "text": "a⁢q+b⁢p=1", "meta": { "altText": "aq+bp=1" } }, ", where ", { "type": "MathFragment", "mathLanguage": "mathml", "text": "a=invp⁢(q)+t⁢p", "meta": { "altText": "a=\\textrm{inv}_{p}(q)+tp" } }, " and ", { "type": "MathFragment", "mathLanguage": "mathml", "text": "b=invq⁢(p)+s⁢q", "meta": { "altText": "b=\\textrm{inv}_{q}(p)+sq" } }, " for some integers ", { "type": "MathFragment", "mathLanguage": "mathml", "text": "s", "meta": { "altText": "s" } }, " and ", { "type": "MathFragment", "mathLanguage": "mathml", "text": "t", "meta": { "altText": "t" } }, ".\nHence, we have" ] }, { "type": "MathBlock", "id": "S3.Ex24", "mathLanguage": "mathml", "text": "invp⁢(q)⁢q+invq⁢(p)⁢p−p⁢q≡1modp⁢q.", "meta": { "altText": "\\displaystyle\\textrm{inv}_{p}(q)q+\\textrm{inv}_{q}(p)p-pq\\equiv 1\\mod pq." } }, { "type": "Paragraph", "content": [ "On the other hand, the left-hand side of the above relation lies in the interval ", { "type": "MathFragment", "mathLanguage": "mathml", "text": "(−p⁢q,p⁢q)", "meta": { "altText": "(-pq,pq)" } }, ". Consequently," ] }, { "type": "MathBlock", "id": "S3.E2", "label": "(2)", "mathLanguage": "mathml", "text": "invp⁢(q)⁢q+invq⁢(p)⁢p=1+p⁢q.", "meta": { "altText": "\\displaystyle\\textrm{inv}_{p}(q)q+\\textrm{inv}_{q}(p)p=1+pq." } }, { "type": "Paragraph", "content": [ "Therefore," ] }, { "type": "MathBlock", "id": "S3.Ex25", "mathLanguage": "mathml", "text": "invp⁢(q)≤p2if and only ifinvq⁢(p)≥q2+1p.", "meta": { "altText": "\\displaystyle\\textrm{inv}_{p}(q)\\leq\\frac{p}{2}\\quad\\textrm{if and only if}\\quad\\textrm{inv}_{q}(p)\\geq\\frac{q}{2}+\\frac{1}{p}." } }, { "type": "Paragraph", "content": [ "However, the right-hand side of the above statement is equivalent to saying that ", { "type": "MathFragment", "mathLanguage": "mathml", "text": "{q}/{2}\" display=\"inline\">invq⁢(p)>q/2", "meta": { "altText": "\\textrm{inv}_{q}(p)>{q}/{2}" } }, "." ] }, { "type": "Paragraph", "content": [ "(b)\nFrom relation (", { "type": "Cite", "target": "S3-E2", "content": [ "2" ] }, ") we deduce for a (rational) number ", { "type": "MathFragment", "mathLanguage": "mathml", "text": "α∈(0,1)", "meta": { "altText": "\\alpha\\in\\nobreak(0,1)" } }, " that" ] }, { "type": "MathBlock", "id": "S3.E3", "label": "(3)", "mathLanguage": "mathml", "text": "invp⁢(q)≤α⁢pif and only ifinvq⁢(p)≥(1−α)⁢q+1p", "meta": { "altText": "\\displaystyle\\textrm{inv}_{p}(q)\\leq\\alpha p\\quad\\textrm{if and only if}\\quad\\textrm{inv}_{q}(p)\\geq(1-\\alpha)q+\\frac{1}{p}" } }, { "type": "Paragraph", "content": [ "and" ] }, { "type": "MathBlock", "id": "S3.E4", "label": "(4)", "mathLanguage": "mathml", "text": "(1-\\alpha)q\\quad\\textrm{if and only if}\\quad\\textrm{inv}_{p}(q)<\\alpha p+\\frac{1}{q}.\" display=\"inline\">invq⁢(p)>(1−α)⁢qif and only ifinvp⁢(q)<α⁢p+1q.", "meta": { "altText": "\\displaystyle\\textrm{inv}_{q}(p)>(1-\\alpha)q\\quad\\textrm{if and only if}\\quad\\textrm{inv}_{p}(q)<\\alpha p+\\frac{1}{q}." } }, { "type": "Paragraph", "content": [ "The first relation shows that" ] }, { "type": "MathBlock", "id": "S3.Ex26", "mathLanguage": "mathml", "text": "(1-\\alpha)q.\" display=\"block\">invp⁢(q)≤α⁢pimpliesinvq⁢(p)>(1−α)⁢q.", "meta": { "altText": "\\textrm{inv}_{p}(q)\\leq\\alpha p\\quad\\textrm{implies}\\quad\\textrm{inv}_{q}(p)>(1-\\alpha)q." } }, { "type": "Paragraph", "content": [ "However, it is clear from the second relation that the converse is not necessarily true.\nIndeed, choose, for example, ", { "type": "MathFragment", "mathLanguage": "mathml", "text": "α=3/7", "meta": { "altText": "\\alpha=3/7" } }, ", ", { "type": "MathFragment", "mathLanguage": "mathml", "text": "p=2", "meta": { "altText": "p=2" } }, " and ", { "type": "MathFragment", "mathLanguage": "mathml", "text": "q=5", "meta": { "altText": "q=5" } }, ".\nThen ", { "type": "MathFragment", "mathLanguage": "mathml", "text": "(1-3/7)5\" display=\"inline\">inv5⁢(2)=3>(1−3/7)⁢5", "meta": { "altText": "\\textrm{inv}_{5}(2)=3>(1-3/7)5" } }, " but ", { "type": "MathFragment", "mathLanguage": "mathml", "text": "(3/7)2\" display=\"inline\">inv2⁢(5)=1>(3/7)⁢2", "meta": { "altText": "\\textrm{inv}_{2}(5)=1>(3/7)2" } }, ".\n\nGenerally, with no additional assumptions, it may happen that ", { "type": "MathFragment", "mathLanguage": "mathml", "text": "α⁢p+1/q", "meta": { "altText": "\\alpha p+\\nobreak 1/q" } }, " is not an integer and ", { "type": "MathFragment", "mathLanguage": "mathml", "text": "\\nobreak\\alpha\np\" display=\"inline\">invp⁢(q)=⌊α⁢p+1/q⌋>α⁢p", "meta": { "altText": "\\textrm{inv}_{p}(q)=\\nobreak\\lfloor\\alpha p+\\nobreak 1/q\\rfloor>\\nobreak\\alpha\np" } }, ".\nHere ", { "type": "MathFragment", "mathLanguage": "mathml", "text": "⌊x⌋", "meta": { "altText": "\\lfloor x\\rfloor" } }, " denotes the largest integer which is less than or equal to the real number ", { "type": "MathFragment", "mathLanguage": "mathml", "text": "x", "meta": { "altText": "x" } }, ".\nIn particular, for rational ", { "type": "MathFragment", "mathLanguage": "mathml", "text": "α", "meta": { "altText": "\\alpha" } }, ", the inequality ", { "type": "MathFragment", "mathLanguage": "mathml", "text": "\\nobreak\\alpha p\" display=\"inline\">⌊α⁢p+1/q⌋>α⁢p", "meta": { "altText": "\\lfloor\\alpha p+\\nobreak 1/q\\rfloor>\\nobreak\\alpha p" } }, " is equivalent to the\ninequality ", { "type": "MathFragment", "mathLanguage": "mathml", "text": "1\" display=\"inline\">{α⁢p}+1/q>1", "meta": { "altText": "\\{\\alpha p\\}+\\nobreak 1/q>1" } }, ", where ", { "type": "MathFragment", "mathLanguage": "mathml", "text": "{x}⁢≔⁢x−⌊x⌋", "meta": { "altText": "\\{x\\}≔\\nobreak x-\\nobreak\\lfloor x\\rfloor" } }, " denotes the\nfractional part of a positive number ", { "type": "MathFragment", "mathLanguage": "mathml", "text": "x", "meta": { "altText": "x" } }, ".\n" ] }, { "type": "Paragraph", "content": [ "(c)\nIn order to prevent the above scenario from happening, we only need to add the assumption ", { "type": "MathFragment", "mathLanguage": "mathml", "text": "q≥v", "meta": { "altText": "q\\geq v" } }, ", ", { "type": "MathFragment", "mathLanguage": "mathml", "text": "v", "meta": { "altText": "v" } }, " being the denominator of ", { "type": "MathFragment", "mathLanguage": "mathml", "text": "α", "meta": { "altText": "\\alpha" } }, ".\nThen, in view of relation (", { "type": "Cite", "target": "S3-E4", "content": [ "4" ] }, "), it suffices to show that" ] }, { "type": "MathBlock", "id": "S3.Ex27", "mathLanguage": "mathml", "text": "invp⁢(q)<α⁢p+1qimpliesinvp⁢(q)≤α⁢p.", "meta": { "altText": "\\textrm{inv}_{p}(q)<\\alpha p+\\frac{1}{q}\\quad\\textrm{implies}\\quad\\textrm{inv}_{p}(q)\\leq\\alpha p." } }, { "type": "Paragraph", "content": [ "Indeed, we readily see that" ] }, { "type": "MathBlock", "id": "S3.Ex28", "mathLanguage": "mathml", "text": "invp⁢(q)<⌊α⁢p⌋+{α⁢p}+1q≤⌊α⁢p⌋+v−1v+1v=⌊α⁢p⌋+1.", "meta": { "altText": "\\textrm{inv}_{p}(q)<\\lfloor\\alpha p\\rfloor+\\{\\alpha p\\}+\\frac{1}{q}\\leq\\lfloor\\alpha p\\rfloor+\\frac{v-1}{v}+\\frac{1}{v}=\\lfloor\\alpha p\\rfloor+1." } }, { "type": "Paragraph", "content": [ "Hence, ", { "type": "MathFragment", "mathLanguage": "mathml", "text": "invp⁢(q)≤⌊α⁢p⌋≤α⁢p", "meta": { "altText": "\\textrm{inv}_{p}(q)\\leq\\lfloor\\alpha p\\rfloor\\leq\\alpha p" } }, ".\n\nWe can instead assume that ", { "type": "MathFragment", "mathLanguage": "mathml", "text": "p≥v", "meta": { "altText": "p\\geq v" } }, " and employ relation (", { "type": "Cite", "target": "S3-E3", "content": [ "3" ] }, ") to prove in a similar fashion the equivalence (", { "type": "Cite", "target": "S3-E1", "content": [ "1" ] }, "). ∎" ] }, { "type": "Heading", "id": "S3.SSx5", "depth": 2, "content": [ "273" ] }, { "type": "Paragraph", "content": [ "Let ", { "type": "MathFragment", "mathLanguage": "mathml", "text": "cn⁢(k)", "meta": { "altText": "c_{n}(k)" } }, " denote the Ramanujan sum defined as the sum of ", { "type": "MathFragment", "mathLanguage": "mathml", "text": "k", "meta": { "altText": "k" } }, "th powers of the primitive ", { "type": "MathFragment", "mathLanguage": "mathml", "text": "n", "meta": { "altText": "n" } }, "th roots of unity.\nShow that, for any integer ", { "type": "MathFragment", "mathLanguage": "mathml", "text": "m≥1", "meta": { "altText": "m\\geq 1" } }, ",\n" ] }, { "type": "MathBlock", "id": "S3.Ex29", "mathLanguage": "mathml", "text": "∑[n,k]=mcn⁢(k)=φ⁢(m),", "meta": { "altText": "\\sum_{[n,k]=m}c_{n}(k)=\\varphi(m)," } }, { "type": "Paragraph", "content": [ "where the sum is over all ordered pairs ", { "type": "MathFragment", "mathLanguage": "mathml", "text": "(n,k)", "meta": { "altText": "(n,k)" } }, " of positive integers ", { "type": "MathFragment", "mathLanguage": "mathml", "text": "n,k", "meta": { "altText": "n,k" } }, " such that their lcm is ", { "type": "MathFragment", "mathLanguage": "mathml", "text": "m", "meta": { "altText": "m" } }, ", and ", { "type": "MathFragment", "mathLanguage": "mathml", "text": "φ", "meta": { "altText": "\\varphi" } }, " is Euler’s totient function." ] }, { "type": "Paragraph", "id": "S3.SSx5.p2", "content": [ { "type": "Emphasis", "content": [ "László Tóth (Department of Mathematics, University of Pécs, Hungary)" ] } ] }, { "type": "Heading", "id": "S3.SSx5.SSSx1", "depth": 3, "content": [ "Proof by the proposer" ] }, { "type": "Paragraph", "content": [ "We use the well-known formula" ] }, { "type": "MathBlock", "id": "S3.Ex30", "mathLanguage": "mathml", "text": "cn⁢(k)=∑d∣(n,k)d⁢μ⁢(n/d),", "meta": { "altText": "c_{n}(k)=\\sum_{d\\mid(n,k)}d\\mu(n/d)," } }, { "type": "Paragraph", "content": [ "where ", { "type": "MathFragment", "mathLanguage": "mathml", "text": "(n,k)", "meta": { "altText": "(n,k)" } }, " is the gcd of ", { "type": "MathFragment", "mathLanguage": "mathml", "text": "n", "meta": { "altText": "n" } }, " and ", { "type": "MathFragment", "mathLanguage": "mathml", "text": "k", "meta": { "altText": "k" } }, ", and ", { "type": "MathFragment", "mathLanguage": "mathml", "text": "μ", "meta": { "altText": "\\mu" } }, " is the Möbius function. Let" ] }, { "type": "MathBlock", "id": "S3.Ex31", "mathLanguage": "mathml", "text": "S⁢(m)⁢≔⁢∑[n,k]=mcn⁢(k).", "meta": { "altText": "S(m)≔\\sum_{[n,k]=m}c_{n}(k)." } }, { "type": "Paragraph", "content": [ "Then for every ", { "type": "MathFragment", "mathLanguage": "mathml", "text": "m≥1", "meta": { "altText": "m\\geq 1" } }, "," ] }, { "type": "MathBlock", "id": "S3.Ex32", "mathLanguage": "mathml", "text": "∑d∣mS⁢(d)=∑d∣m∑[n,k]=dcn⁢(k)=∑[n,k]∣mcn⁢(k)", "meta": { "altText": "\\displaystyle\\sum_{d\\mid m}S(d)=\\sum_{d\\mid m}\\sum_{[n,k]=d}c_{n}(k)=\\sum_{[n,k]\\mid m}c_{n}(k)" } }, { "type": "MathBlock", "id": "S3.Ex33", "mathLanguage": "mathml", "text": "=∑[n,k]∣m∑δ∣(n,k)δ⁢μ⁢(n/δ)=∑n∣m,k∣m∑δ∣n,δ∣kδ⁢μ⁢(n/δ)", "meta": { "altText": "\\displaystyle=\\sum_{[n,k]\\mid m}\\,\\sum_{\\delta\\mid(n,k)}\\delta\\mu(n/\\delta)=\\sum_{n\\mid m,\\,k\\mid m}\\,\\sum_{\\delta\\mid n,\\,\\delta\\mid k}\\delta\\mu(n/\\delta)" } }, { "type": "MathBlock", "id": "S3.Ex34", "mathLanguage": "mathml", "text": "=∑δ⁢a⁢j=δ⁢b⁢ℓ=mδ⁢μ⁢(j)=∑δ⁢t=mδ⁢(∑a⁢j=tμ⁢(j))⁢(∑b⁢ℓ=t1).", "meta": { "altText": "\\displaystyle=\\sum_{\\delta aj=\\delta b\\ell=m}\\delta\\mu(j)=\\sum_{\\delta t=m}\\delta\\mkern 2.0mu\\biggl(\\mkern 2.0mu\\sum_{aj=t}\\mu(j)\\biggr)\\biggl(\\mkern 2.0mu\\sum_{b\\ell=t}1\\biggr)." } }, { "type": "Paragraph", "content": [ "Here" ] }, { "type": "MathBlock", "id": "S3.Ex35", "mathLanguage": "mathml", "text": "1$},\\end{cases}\" display=\"block\">∑a⁢j=tμ⁢(j)={1,if t=1,0,if t>1,", "meta": { "altText": "\\sum_{aj=t}\\mu(j)=\\begin{cases}1,&\\textrm{if $t=1$},\\\\\n0,&\\textrm{if $t>1$},\\end{cases}" } }, { "type": "Paragraph", "content": [ "and this gives" ] }, { "type": "MathBlock", "id": "S3.Ex36", "mathLanguage": "mathml", "text": "∑d∣mS⁢(d)=m.", "meta": { "altText": "\\sum_{d\\mid m}S(d)=m." } }, { "type": "Paragraph", "id": "S3.SSx5.SSSx1.p3", "content": [ "Consequently, ", { "type": "MathFragment", "mathLanguage": "mathml", "text": "S⁢(m)=φ⁢(m)", "meta": { "altText": "S(m)=\\varphi(m)" } }, ", by Möbius inversion." ] }, { "type": "Paragraph", "content": [ "Alternatively, one can show that ", { "type": "MathFragment", "mathLanguage": "mathml", "text": "S⁢(m)", "meta": { "altText": "S(m)" } }, " is multiplicative in ", { "type": "MathFragment", "mathLanguage": "mathml", "text": "m", "meta": { "altText": "m" } }, ", and" ] }, { "type": "MathBlock", "id": "S3.Ex37", "mathLanguage": "mathml", "text": "S⁢(pe)=pe−1⁢(p−1)=φ⁢(pe)", "meta": { "altText": "S(p^{e})=p^{e-1}(p-1)=\\varphi(p^{e})" } }, { "type": "Paragraph", "content": [ "for any prime power ", { "type": "MathFragment", "mathLanguage": "mathml", "text": "pe", "meta": { "altText": "p^{e}" } }, " (", { "type": "MathFragment", "mathLanguage": "mathml", "text": "e≥1", "meta": { "altText": "e\\geq 1" } }, "). ∎" ] }, { "type": "Heading", "id": "S3.SSx5.SSSx2", "depth": 3, "content": [ "Remarks" ] }, { "type": "Paragraph", "content": [ "If ", { "type": "MathFragment", "mathLanguage": "mathml", "text": "F⁢(n,k)", "meta": { "altText": "F(n,k)" } }, " is an arbitrary function of two variables, then" ] }, { "type": "MathBlock", "id": "S3.Ex38", "mathLanguage": "mathml", "text": "∑[n,k]=mF⁢(n,k)", "meta": { "altText": "\\sum_{[n,k]=m}F(n,k)" } }, { "type": "Paragraph", "content": [ "is called the lcm-convolute of the function ", { "type": "MathFragment", "mathLanguage": "mathml", "text": "F", "meta": { "altText": "F" } }, ". Another example is" ] }, { "type": "MathBlock", "id": "S3.Ex39", "mathLanguage": "mathml", "text": "c⁢(m)=∑[n,k]=m(n,k),", "meta": { "altText": "c(m)=\\sum_{[n,k]=m}(n,k)," } }, { "type": "Paragraph", "content": [ "representing the number of cyclic subgroups of the group ", { "type": "MathFragment", "mathLanguage": "mathml", "text": "ℤm×ℤm", "meta": { "altText": "{\\mathbb{Z}}_{m}\\times{\\mathbb{Z}}_{m}" } }, "." ] }, { "type": "Paragraph", "content": [ "More generally, if ", { "type": "MathFragment", "mathLanguage": "mathml", "text": "F⁢(n1,…,nr)", "meta": { "altText": "F(n_{1},\\ldots,n_{r})" } }, " is a function of ", { "type": "MathFragment", "mathLanguage": "mathml", "text": "r≥2", "meta": { "altText": "r\\geq 2" } }, " variables, then the lcm-convolute\nof ", { "type": "MathFragment", "mathLanguage": "mathml", "text": "F", "meta": { "altText": "F" } }, " is" ] }, { "type": "MathBlock", "id": "S3.Ex40", "mathLanguage": "mathml", "text": "SF⁢(m)=∑[n1,…,nr]=mF⁢(n1,…,nr).", "meta": { "altText": "S_{F}(m)=\\sum_{[n_{1},\\ldots,n_{r}]=m}F(n_{1},\\ldots,n_{r})." } }, { "type": "Paragraph", "id": "S3.SSx5.SSSx2.p3", "content": [ "It can be shown that if ", { "type": "MathFragment", "mathLanguage": "mathml", "text": "F", "meta": { "altText": "F" } }, " is multiplicative as a function of ", { "type": "MathFragment", "mathLanguage": "mathml", "text": "r", "meta": { "altText": "r" } }, " variables, then ", { "type": "MathFragment", "mathLanguage": "mathml", "text": "SF⁢(m)", "meta": { "altText": "S_{F}(m)" } }, " is\nmultiplicative in ", { "type": "MathFragment", "mathLanguage": "mathml", "text": "m", "meta": { "altText": "m" } }, ". See [", { "type": "Cite", "target": "bib-bib1", "content": [ "1" ] }, ", Section 6] for some more details." ] }, { "type": "Heading", "id": "S3.SSx6", "depth": 2, "content": [ "274" ] }, { "type": "Paragraph", "content": [ "Show that, for every integer ", { "type": "MathFragment", "mathLanguage": "mathml", "text": "n≥1", "meta": { "altText": "n\\geq 1" } }, ", we have the polynomial identity" ] }, { "type": "MathBlock", "id": "S3.Ex41", "mathLanguage": "mathml", "text": "∏k=1(k,n)=1n(x(k−1,n)−1)=∏d∣nΦd⁢(x)φ⁢(n)/φ⁢(d),", "meta": { "altText": "\\prod_{\\begin{subarray}{c}k=1\\\\\n(k,n)=1\\end{subarray}}^{n}(x^{(k-1,n)}-1)=\\prod_{d\\mid n}\\Phi_{d}(x)^{\\varphi(n)/\\varphi(d)}," } }, { "type": "Paragraph", "content": [ "where ", { "type": "MathFragment", "mathLanguage": "mathml", "text": "Φd⁢(x)", "meta": { "altText": "\\Phi_{d}(x)" } }, " are the cyclotomic polynomials and ", { "type": "MathFragment", "mathLanguage": "mathml", "text": "φ", "meta": { "altText": "\\varphi" } }, " denotes Euler’s totient function." ] }, { "type": "Paragraph", "id": "S3.SSx6.p2", "content": [ { "type": "Emphasis", "content": [ "László Tóth (Department of Mathematics, University of Pécs, Hungary)" ] } ] }, { "type": "Heading", "id": "S3.SSx6.SSSx1", "depth": 3, "content": [ "Proof by the proposer" ] }, { "type": "Paragraph", "content": [ "More generally, let ", { "type": "MathFragment", "mathLanguage": "mathml", "text": "f:ℕ→ℂ", "meta": { "altText": "f\\colon\\mathbb{N}\\to\\mathbb{C}" } }, " be an arbitrary arithmetic function. We show that, for any ", { "type": "MathFragment", "mathLanguage": "mathml", "text": "n≥1", "meta": { "altText": "n\\geq 1" } }, "," ] }, { "type": "MathBlock", "id": "S3.E5", "label": "(5)", "mathLanguage": "mathml", "text": "Mf⁢(n)⁢≔⁢∑k=1(k,n)=1nf⁢((k−1,n))=φ⁢(n)⁢∑d∣n(μ*f)⁢(d)φ⁢(d),", "meta": { "altText": "M_{f}(n)≔\\sum_{\\begin{subarray}{c}k=1\\\\\n(k,n)=1\\end{subarray}}^{n}f((k-1,n))=\\varphi(n)\\sum_{d\\mid n}\\frac{(\\mu*f)(d)}{\\varphi(d)}," } }, { "type": "Paragraph", "content": [ "where ", { "type": "MathFragment", "mathLanguage": "mathml", "text": "μ", "meta": { "altText": "\\mu" } }, " is the Möbius function and ", { "type": "MathFragment", "mathLanguage": "mathml", "text": "*", "meta": { "altText": "*" } }, " denotes the Dirichlet convolution of arithmetic functions." ] }, { "type": "Paragraph", "content": [ "By taking (formally) ", { "type": "MathFragment", "mathLanguage": "mathml", "text": "f⁢(n)⁢≔⁢log⁡(xn−1)", "meta": { "altText": "f(n)≔\\log(x^{n}-1)" } }, " and using the well-known identity" ] }, { "type": "MathBlock", "id": "S3.Ex42", "mathLanguage": "mathml", "text": "xn−1=∏d∣nΦd⁢(x),", "meta": { "altText": "x^{n}-1=\\prod_{d\\mid n}\\Phi_{d}(x)," } }, { "type": "Paragraph", "content": [ "we deduce that" ] }, { "type": "MathBlock", "id": "S3.Ex43", "mathLanguage": "mathml", "text": "f⁢(n)=log⁡(xn−1)=∑d∣nlog⁡Φd⁢(x),", "meta": { "altText": "f(n)=\\log(x^{n}-1)=\\sum_{d\\mid n}\\log\\Phi_{d}(x)," } }, { "type": "Paragraph", "content": [ "that is, by Möbius inversion," ] }, { "type": "MathBlock", "id": "S3.Ex44", "mathLanguage": "mathml", "text": "(μ*f)⁢(n)=log⁡Φn⁢(x),", "meta": { "altText": "(\\mu*f)(n)=\\log\\Phi_{n}(x)," } }, { "type": "Paragraph", "content": [ "and identity (", { "type": "Cite", "target": "S3-E5", "content": [ "5" ] }, ") gives" ] }, { "type": "MathBlock", "id": "S3.Ex45", "mathLanguage": "mathml", "text": "∑k=1(k,n)=1nlog⁡(x(k−1,n)−1)=φ⁢(n)⁢∑d∣nlog⁡Φd⁢(x)φ⁢(d),", "meta": { "altText": "\\sum_{\\begin{subarray}{c}k=1\\\\\n(k,n)=1\\end{subarray}}^{n}\\log\\bigl(x^{(k-1,n)}-1\\bigr)=\\varphi(n)\\sum_{d\\mid n}\\frac{\\log\\Phi_{d}(x)}{\\varphi(d)}," } }, { "type": "Paragraph", "content": [ "which is equivalent to the identity to be proved." ] }, { "type": "Paragraph", "content": [ "Now to prove the general identity (", { "type": "Cite", "target": "S3-E5", "content": [ "5" ] }, ") write" ] }, { "type": "MathBlock", "id": "S3.Ex46", "mathLanguage": "mathml", "text": "Mf⁢(n)=∑k=1nf⁢((k−1,n))⁢∑d∣(k,n)μ⁢(d)", "meta": { "altText": "\\displaystyle M_{f}(n)=\\sum_{k=1}^{n}f((k-1,n))\\sum_{d\\mid(k,n)}\\mu(d)" } }, { "type": "MathBlock", "id": "S3.Ex49", "mathLanguage": "mathml", "text": "=∑d∣nμ⁢(d)⁢∑k=1d∣knf⁢((k−1,n)).", "meta": { "altText": "\\displaystyle=\\sum_{d\\mid n}\\mu(d)\\sum_{\\begin{subarray}{c}k=1\\\\\nd\\mid k\\end{subarray}}^{n}f((k-1,n))." } }, { "type": "Paragraph", "content": [ "By using that ", { "type": "MathFragment", "mathLanguage": "mathml", "text": "f⁢(n)=∑d∣n(μ*f)⁢(d)", "meta": { "altText": "f(n)=\\sum_{d\\mid n}(\\mu*f)(d)" } }, " (", { "type": "MathFragment", "mathLanguage": "mathml", "text": "n≥1", "meta": { "altText": "n\\geq 1" } }, "), we deduce that" ] }, { "type": "MathBlock", "id": "S3.Ex52", "mathLanguage": "mathml", "text": "A⁢≔⁢∑k=1d∣knf⁢((k−1,n))=∑j=1n/df⁢((j⁢d−1,n))", "meta": { "altText": "\\displaystyle A≔\\sum_{\\begin{subarray}{c}k=1\\\\\nd\\mid k\\end{subarray}}^{n}f((k-1,n))=\\sum_{j=1}^{n/d}f((jd-1,n))" } }, { "type": "MathBlock", "id": "S3.Ex55", "mathLanguage": "mathml", "text": "=∑j=1n/d∑e∣jd−1,e∣n(μ*f)⁢(e)=∑e∣n(μ*f)⁢(e)⁢∑j=1j⁢d≡1⁢(mod e)n/d1,", "meta": { "altText": "\\displaystyle=\\sum_{j=1}^{n/d}\\,\\sum_{e\\mid jd-1,\\,e\\mid n}(\\mu*f)(e)=\\sum_{e\\mid n}(\\mu*f)(e)\\sum_{\\begin{subarray}{c}j=1\\\\\njd\\equiv 1\\,\\textrm{(mod $e$)}\\end{subarray}}^{n/d}1," } }, { "type": "Paragraph", "content": [ "where the inner sum is ", { "type": "MathFragment", "mathLanguage": "mathml", "text": "n/(d⁢e)", "meta": { "altText": "n/(de)" } }, " if ", { "type": "MathFragment", "mathLanguage": "mathml", "text": "(d,e)=1", "meta": { "altText": "(d,e)=1" } }, " and ", { "type": "MathFragment", "mathLanguage": "mathml", "text": "0", "meta": { "altText": "0" } }, " otherwise. This gives" ] }, { "type": "MathBlock", "id": "S3.Ex56", "mathLanguage": "mathml", "text": "A=∑e∣n(e,d)=1(μ*f)⁢(e)⋅nd⁢e=nd⁢∑e∣n(e,d)=1(μ*f)⁢(e)e.", "meta": { "altText": "A=\\sum_{\\begin{subarray}{c}e\\mid n\\\\\n(e,d)=1\\end{subarray}}(\\mu*f)(e)\\cdot\\frac{n}{de}=\\frac{n}{d}\\sum_{\\begin{subarray}{c}e\\mid n\\\\\n(e,d)=1\\end{subarray}}\\frac{(\\mu*f)(e)}{e}." } }, { "type": "Paragraph", "content": [ "Thus," ] }, { "type": "MathBlock", "id": "S3.Ex57", "mathLanguage": "mathml", "text": "Mf⁢(n)=∑d∣nμ⁢(d)⁢nd⁢∑e∣n(e,d)=1(μ*f)⁢(e)e=n⁢∑e∣n(μ*f)⁢(e)e⁢∑d∣n(d,e)=1μ⁢(d)d,", "meta": { "altText": "M_{f}(n)=\\sum_{d\\mid n}\\mu(d)\\frac{n}{d}\\mkern-2.0mu\\mkern-2.0mu\\sum_{\\begin{subarray}{c}e\\mid n\\\\\n(e,d){=}1\\end{subarray}}\\mkern-2.0mu\\mkern-2.0mu\\mkern-2.0mu\\mkern-2.0mu\\frac{(\\mu*f)(e)}{e}=n\\sum_{e\\mid n}\\frac{(\\mu*f)(e)}{e}\\mkern-2.0mu\\mkern-2.0mu\\sum_{\\begin{subarray}{c}d\\mid n\\\\\n(d,e){=}1\\end{subarray}}\\mkern-2.0mu\\mkern-2.0mu\\mkern-2.0mu\\frac{\\mu(d)}{d}," } }, { "type": "Paragraph", "content": [ "with" ] }, { "type": "MathBlock", "id": "S3.Ex62", "mathLanguage": "mathml", "text": "∑d∣n(d,e)=1μ⁢(d)d=∏p∣np∤e(1−1p)", "meta": { "altText": "\\displaystyle\\sum_{\\begin{subarray}{c}d\\mid n\\\\\n(d,e)=1\\end{subarray}}\\frac{\\mu(d)}{d}=\\prod_{\\begin{subarray}{c}p\\mid n\\\\\np\\nmid e\\end{subarray}}\\Bigl(1-\\frac{1}{p}\\Bigr)" } }, { "type": "MathBlock", "id": "S3.Ex63", "mathLanguage": "mathml", "text": "=∏p∣n(1−1p)⁢∏p∣e(1−1p)−1=φ⁢(n)n⋅eφ⁢(e).", "meta": { "altText": "\\displaystyle=\\prod_{p\\mid n}\\Bigl(1-\\frac{1}{p}\\Bigr)\\prod_{p\\mid e}\\Bigl(1-\\frac{1}{p}\\Bigr)^{-1}=\\frac{\\varphi(n)}{n}\\cdot\\frac{e}{\\varphi(e)}." } }, { "type": "Paragraph", "content": [ "Consequently," ] }, { "type": "MathBlock", "id": "S3.Ex64", "mathLanguage": "mathml", "text": "Mf⁢(n)=φ⁢(n)⁢∑e∣n(μ*f)⁢(e)φ⁢(e),", "meta": { "altText": "M_{f}(n)=\\varphi(n)\\sum_{e\\mid n}\\frac{(\\mu*f)(e)}{\\varphi(e)}," } }, { "type": "Paragraph", "content": [ "which is identity (", { "type": "Cite", "target": "S3-E5", "content": [ "5" ] }, "). ∎" ] }, { "type": "Heading", "id": "S3.SSx6.SSSx2", "depth": 3, "content": [ "Remarks" ] }, { "type": "Paragraph", "content": [ "If ", { "type": "MathFragment", "mathLanguage": "mathml", "text": "f⁢(n)=n", "meta": { "altText": "f(n)=n" } }, " (", { "type": "MathFragment", "mathLanguage": "mathml", "text": "n≥1", "meta": { "altText": "n\\geq 1" } }, "), then (", { "type": "Cite", "target": "S3-E5", "content": [ "5" ] }, ") reduces to Menon’s identity" ] }, { "type": "MathBlock", "id": "S3.Ex65", "mathLanguage": "mathml", "text": "∑k=1(k,n)=1n(k−1,n)=φ⁢(n)⁢τ⁢(n),", "meta": { "altText": "\\sum_{\\begin{subarray}{c}k=1\\\\\n(k,n)=1\\end{subarray}}^{n}(k-1,n)=\\varphi(n)\\tau(n)," } }, { "type": "Paragraph", "content": [ "where ", { "type": "MathFragment", "mathLanguage": "mathml", "text": "τ⁢(n)=∑d∣n1", "meta": { "altText": "\\tau(n)=\\sum_{d\\mid n}1" } }, ". See [", { "type": "Cite", "target": "bib-bib2", "content": [ "2" ] }, "] for references, other generalizations and analogs\nof these arithmetic identities." ] }, { "type": "Paragraph", "id": "p2", "content": [ "We wait to receive your solutions to the proposed problems and ideas on the open problems. Send your solutions to Michael Th. Rassias by email to ", { "type": "Link", "target": "mailto:mthrassias@yahoo.com", "content": [ "mthrassias@yahoo.com" ] }, "." ] }, { "type": "Paragraph", "id": "p3", "content": [ "We also solicit your new problems with their solutions for the next “Solved and unsolved problems” column, which will\nbe devoted to ", { "type": "Emphasis", "content": [ "probability theory" ] }, "." ] } ] }