Recent zbMATH articles in MSC 11Yhttps://www.zbmath.org/atom/cc/11Y2021-04-16T16:22:00+00:00WerkzeugPerfect triangles on the curve \(C_4\).https://www.zbmath.org/1456.112362021-04-16T16:22:00+00:00"Ismail, Shahrina"https://www.zbmath.org/authors/?q=ai:ismail.shahrinaA triangle with the three sides \((a,b,c)\), the three medians \((k,l,m)\) and the area \(\Delta\) is called a Heron triangle if \(a,b,c\) and \(\Delta\) are rational. If each of the \(7\) mentioned parameters is rational, the triangle is called perfect. While finding a perfect triangle is still an open problem, it has been shown in previous work that Heron triangles with two rational medians can be parametrized by eight curves \(C_1,\ldots, C_8\). The main contribution of this paper is to prove that no perfect triangle arises from the curve \(C_4\), except possibly for one case that could not have been eliminated by the proposed methodology, and thus remains a prospect for future work.
The author starts by showing that finding a perfect triangle arising from \(C_4\) is equivalent to finding integers \(n\) such that \(Z(nP)\) is square, where \(Z(x,y)=R(x)-S(x)y\) for two explicitly defined polynomials \(R\) and \(S\), and \(P\) is an infinite-order generator of a certain elliptic curve. This consideration leads to a set \(Y\) of small candidates for \(n\), for which it is checked that no perfect triangle arises from them. Based on the elements of \(Y\), restrictions are imposed on the lifting to larger multiples of the point \(P\). This technique, which may be considered as an inductive method for the Mordell-Weil sieve, allows to eliminate all candidates for \(n\) except those relating to the value \(-2\in Y\). The author also mentions that a perfect triangle arising from this exceptional case would have to have side lengths at least \(10^{10^{10}}\).
The main result of the paper is an interesting and valuable contribution to the open problem of the existence of perfect triangles. With regard to the readability of the paper, I believe that it would have benefited from more detailed explanations of the ideas and the strategy. I also noticed some minor inconsistencies. For example, the claim about \(Z(nP)\) being square appears to be missing in the formulation of Theorem 2.1, and the formulation of Theorem 3.4 appears to contradict what it actually should say in order to conform with Table 1 and its application in the proof of Theorem 6.1. However, most parts of the paper are well-written, in particular the presentation of the problem and the state-of-the-art in the introduction.
Reviewer: Markus Hittmeir (Wien)On the scalar complexity of Chudnovsky\(^2\) multiplication algorithm in finite fields.https://www.zbmath.org/1456.112352021-04-16T16:22:00+00:00"Ballet, Stéphane"https://www.zbmath.org/authors/?q=ai:ballet.stephane"Bonnecaze, Alexis"https://www.zbmath.org/authors/?q=ai:bonnecaze.alexis"Dang, Thanh-Hung"https://www.zbmath.org/authors/?q=ai:dang.thanh-hungThe paper under review deals with the multiplicative complexity of multiplication in a finite field \(F_{q^n}\) which is the number of multiplications required to multiply in the \(F_q\)-vector space \(F_{q^n}\). The types of multiplications in \(F_q\) are the scalar multiplication and the bilinear one. The scalar multiplication is
the multiplication by a constant in \(F_q\). The bilinear multiplication is a multiplication that depends on the elements of \(F_{q^n}\) that are multiplied. D. V. and G. V. Chudnovsky, generalizing interpolation algorithms on the projective line over \(F_q\) to algebraic curves of higher genus over \(F_q\), provided a method which enabled to prove the linearity of the bilinear complexity of multiplication in finite extensions
of a finite field [\textit{D. V. Chudnovsky} and \textit{G. V. Chudnovsky}, J. Complexity 4, No. 4, 285--316 (1988; Zbl 0668.68040)]. This is the so-called Chudnovsky\(^2\) algorithm.
In this paper, a new method of construction with an objective to reduce the scalar complexity of Chudnovsky\(^2\) multiplication algorithms is proposed. An optimized basis representation of the Riemann-Roch space \(L(2D)\) is sought in order to minimize the number of scalar multiplications in the algorithm.
In particular, the Baum-Shokrollahi construction for multiplication in \(F_{256}/F_4\) based on the elliptic Fermat curve \(x^3 + y^3 = 1\) is improved.
For the entire collection see [Zbl 1428.68013].
Reviewer: Dimitros Poulakis (Thessaloniki)A rigorous extension of the Schönhage-Strassen integer multiplication algorithm using complex interval arithmetic.https://www.zbmath.org/1456.682322021-04-16T16:22:00+00:00"Steinke, Thomas"https://www.zbmath.org/authors/?q=ai:steinke.thomas"Sainudiin, Raazesh"https://www.zbmath.org/authors/?q=ai:sainudiin.raazeshSummary: Multiplication of \(n\)-digit integers by long multiplication requires \(O(n^2)\) operations and can be time-consuming. In [Computing 7, 281--292 (1971; Zbl 0223.68007)] \textit{A. Schönhage} and \textit{V. Strassen} published an algorithm capable of performing the task with only \(O(n\log(n))\) arithmetic operations over the complex field \(\mathbb{C}\); naturally, finite-precision approximations to \(\mathbb{C}\) are used and rounding errors need to be accounted for. Overall, using variable-precision fixed-point numbers, this results in an \(O(n(\log(n))^{(2+\epsilon)})\)-time algorithm. However, to make this algorithm more efficient and practical we need to make use of hardware-based floating-point numbers. How do we deal with rounding errors? and how do we determine the limits of the fixed-precision hardware? Our solution is to use interval arithmetic to guarantee the correctness of results and determine the hardware's limits. We examine the feasibility of this approach and are able to report that 75,000-digit base-256 integers can be handled using double-precision containment sets. This clearly demonstrates that our approach has practical potential; however, at this stage, our implementation does not yet compete with commercial ones, but we are able to demonstrate the feasibility of this technique.
For the entire collection see [Zbl 1391.03010].Modular polynomials on Hilbert surfaces.https://www.zbmath.org/1456.110782021-04-16T16:22:00+00:00"Milio, Enea"https://www.zbmath.org/authors/?q=ai:milio.enea"Robert, Damien"https://www.zbmath.org/authors/?q=ai:robert.damienSummary: We describe an evaluation/interpolation approach to compute modular polynomials on a Hilbert surface, which parametrizes abelian surfaces with maximal real multiplication. Under some heuristics we obtain a quasi-linear algorithm. The corresponding modular polynomials are much smaller than the ones on the Siegel threefold. We explain how to compute even smaller polynomials by using pullbacks of theta functions to the Hilbert surface.Self-replication and Borwein-like algorithms.https://www.zbmath.org/1456.112382021-04-16T16:22:00+00:00"Guillera, Jesús"https://www.zbmath.org/authors/?q=ai:guillera.jesusSummary: Using a self-replicating method, we generalize with a free parameter some Borwein algorithms for the number \(\pi\). This generalization includes values of the gamma function like \(\Gamma (1/3)\), \(\Gamma (1/4)\), and of course \(\Gamma (1/2)=\sqrt{\pi}\). In addition, we give new rapid algorithms for the perimeter of an ellipse.Primality testing of Woodall numbers.https://www.zbmath.org/1456.112342021-04-16T16:22:00+00:00"Azami, Kazuki"https://www.zbmath.org/authors/?q=ai:azami.kazuki"Uchiyama, Shigenori"https://www.zbmath.org/authors/?q=ai:uchiyama.shigenoriSummary: In 1969, Riesel proposed a primality test for natural numbers of the form \(h \cdot 2^n-1\), which includes the case \(h=n\), the Woodall numbers \(W_ {n} = n \cdot 2 ^ {n} -1\). In this paper, we utilize Riesel's primality test for Woodall numbers, and propose a primality testing algorithm for Woodall numbers. The implementations of the algorithm and its optimization are discussed.Precise error estimate of the Brent-McMillan algorithm for Euler's constant.https://www.zbmath.org/1456.330062021-04-16T16:22:00+00:00"Demailly, Jean-Pierre"https://www.zbmath.org/authors/?q=ai:demailly.jean-pierreSummary: \textit{R. P. Brent} and \textit{E. M. McMillan} [Math. Comput. 34, 305--312 (1980; Zbl 0442.10002)] introduced in 1980 a new algorithm for the computation of Euler's constant \(\gamma\), based on the use of the Bessel functions \(I_0(x)\) and \(K_0(x)\). It is the fastest known algorithm for the computation of \(\gamma\). The time complexity can still be improved by evaluating a certain divergent asymptotic expansion up to its minimal term. Brent-McMillan conjectured in 1980 that the error is of the same magnitude as the last computed term, and \textit{R. P. Brent} and \textit{F. Johansson} [Math. Comput. 84, No. 295, 2351--2359 (2015; Zbl 1320.33007)] partially proved it in 2015. They also gave some numerical evidence for a more precise estimate of the error term. We find here an explicit expression of that optimal estimate, along with a complete self-contained formal proof and an even more precise error bound.A value region problem for continued fractions and discrete Dirac equations.https://www.zbmath.org/1456.300072021-04-16T16:22:00+00:00"Klimek, Slawomir"https://www.zbmath.org/authors/?q=ai:klimek.slawomir"McBride, Matt"https://www.zbmath.org/authors/?q=ai:mcbride.matt"Rathnayake, Sumedha"https://www.zbmath.org/authors/?q=ai:rathnayake.sumedha"Sakai, Kaoru"https://www.zbmath.org/authors/?q=ai:sakai.kaoruSummary: Motivated by applications in noncommutative geometry we prove several value range estimates for even convergents and tails, and odd reverse sequences of Stieltjes type continued fractions with bounded ratio of consecutive elements, and show how those estimates control growth of solutions of a system of discrete Dirac equations.Apéry type recurrence relations.https://www.zbmath.org/1456.110172021-04-16T16:22:00+00:00"Centurión Fajardo, Alicia María"https://www.zbmath.org/authors/?q=ai:centurion-fajardo.alicia-maria"Céspedes Trujillo, Nancy"https://www.zbmath.org/authors/?q=ai:cespedes-trujillo.nancy"Moreno Roque, Eduardo"https://www.zbmath.org/authors/?q=ai:moreno-roque.eduardoSummary: In the last decade, the study of recurrence relations has obtained great relevance. The generation of rational approximants has been favored with the inclusion of recurrence relations for the study of the irrationality of certain mathematical constants, in particular Apéry's constant. This article presents, based on the Zeilberger algorithm, two recurrence relations of the Apéry type. For the result, the denominators of the rational approximations to the Apéry constant were modified.Quantum algorithms for the approximate \(k\)-list problem and their application to lattice sieving.https://www.zbmath.org/1456.940932021-04-16T16:22:00+00:00"Kirshanova, Elena"https://www.zbmath.org/authors/?q=ai:kirshanova.elena"Mårtensson, Erik"https://www.zbmath.org/authors/?q=ai:martensson.erik"Postlethwaite, Eamonn W."https://www.zbmath.org/authors/?q=ai:postlethwaite.eamonn-w"Moulik, Subhayan Roy"https://www.zbmath.org/authors/?q=ai:moulik.subhayan-roySummary: The Shortest Vector problem (SVP) is one of the mathematical foundations of lattice based cryptography. Lattice sieve algorithms are amongst the foremost methods of solving SVP. The asymptotically fastest known classical and quantum sieves solve SVP in a \(d\)-dimensional lattice in \(2^{\mathsf{c}d+o(d)}\) time steps with \(2^{\mathsf{c}^\prime d+o(d)}\) memory for constants \(c, c^\prime\). In this work, we give various quantum sieving algorithms that trade computational steps for memory.
We first give a quantum analogue of the classical \(k\)-Sieve algorithm [\textit{G. Herold} et al., Lect. Notes Comput. Sci. 10769, 407--436 (2018; Zbl 1439.94033)] in the quantum random access memory (QRAM) model, achieving an algorithm that heuristically solves SVP in \(2^{0.2989d+o(d)}\) time steps using \(2^{0.1395d+o(d)}\) memory. This should be compared to the state-of-the-art algorithm [\textit{T. Laarhoven} [Search problems in cryptography. Eindhoven University of Technology (PhD Thesis) (2015)] which, in the same model, solves SVP in \(2^{0.2653d+o(d)}\) time steps and memory. In the QRAM model these algorithms can be implemented using \(\mathrm{poly}(d)\) width quantum circuits. Secondly, we frame the \(k\)-Sieve as the problem of \(k\)-clique listing in a graph and apply quantum \(k\)-clique finding techniques to the \(k\)-Sieve.
Finally, we explore the large quantum memory regime by adapting parallel quantum search [\textit{R. Beals} et al., Proc. R. Soc. Lond., Ser. A, Math. Phys. Eng. Sci. 469, No. 2153, Article ID 20120686, 20 p. (2013; Zbl 1371.81074)] to the 2-Sieve, and give an analysis in the quantum circuit model. We show how to solve SVP in \(2^{0.1037d+o(d)}\) time steps using \(2^{0.2075d+o(d)}\) quantum memory.
For the entire collection see [Zbl 1428.94008].The conjugacy problem in \(\mathrm{ Gl } ( n, \mathbb{Z} )\).https://www.zbmath.org/1456.200042021-04-16T16:22:00+00:00"Eick, Bettina"https://www.zbmath.org/authors/?q=ai:eick.bettina"Hofmann, Tommy"https://www.zbmath.org/authors/?q=ai:hofmann.tommy"O'Brien, E. A."https://www.zbmath.org/authors/?q=ai:obrien.eamonn-aLet \(T\) and \(U\) be elements of \(\mathrm{GL}(n,\mathbb{Q})\). The \textit{rational conjugacy problem} asks if there exists \(X\in\mathrm{GL}(n, \mathbb{Q})\) such that \(XTX^{-1}=U\). It is well known that this can be decided effectively by computing and comparing the rational canonical forms of \(T\) and \(U\). More difficult is the \textit{integral conjugacy problem}: decide whether there exists \(X\in\mathrm{GL}(n,\mathbb{Z})\) with \(XTX^{-1}=U\). Associated to the integral conjugacy problem is the \textit{centraliser problem}: determine a generating set for \(C_{\mathbb{Z}}(T)=\{X\in\mathrm{GL}(n,\mathbb{Z}) \mid XTX^{-1}=T\}\). Since \(C_{\mathbb{Z}}(T)\) is arithmetic, the work of \textit{F. Grunewald} and \textit{D. Segal} [Ann. Math. (2) 112, 531--583 (1980; Zbl 0457.20047)] implies that it is both finitely generated and finitely presented. But no practical algorithm to compute a finite generating set for an arithmetic group is known.
In the article under review, the authors present a new algorithm that, given two matrices in \(\mathrm{GL}(n,\mathbb{Q})\), decides if they are conjugate in \(\mathrm{GL}(n, \mathbb{Z})\) and, if so, determines a conjugating matrix. They also give an algorithm to construct a generating set for \(C_{\mathbb{Z}}(T)\) for \(T \in\mathrm{GL}(n,\mathbb{Q})\). To do this they reduce these problems, respectively, to the isomorphism and automorphism group problems for certain modules over rings of the form \(\mathcal{O}_{K}[y]/(y^{\ell})\), where \(\mathcal{O}_{K}\) is the maximal order of an algebraic number field \(K\) and \(\ell \in \mathbb{N}\), and then provide algorithms to solve the latter. The algorithms are effective and usable in practice, the authors provide their implementation using the MAGMA software.
Reviewer: Enrico Jabara (Venezia)An algorithm for solving a quartic Diophantine equation satisfying Runge's condition.https://www.zbmath.org/1456.112372021-04-16T16:22:00+00:00"Osipov, N. N."https://www.zbmath.org/authors/?q=ai:osipov.nikolay-n|osipov.nikolai-n"Dalinkevich, S. D."https://www.zbmath.org/authors/?q=ai:dalinkevich.s-dThe classical method of \textit{ C. Runge} [J. Reine Angew. Math. 100, 425--435 (1887; JFM 19.0076.03)] is well known in diophantine number theory, see also \textit{ P. G. Walsh} [Acta Arith. 62, No. 2, 157--172 (1992; Zbl 0769.11017)]. The scope of equations that can be solved using this method is although restricted, but it extends also to surprising cases. Moreover, the resolution of these equations might be very efficient.
For cubic equations \textit{ N. N. Osipov} and \textit{B. V. Gulnova} [J. Sib. Fed. Univ. Math. Phys. 11, No. 2, 137--147 (2018; Zbl 07325400)] gave a practical algorithm which is extended in the present paper to certain quartic equations by the authors. Moreover, the algorithm is implemented in the computer algebra system PARI/GP.
For the entire collection see [Zbl 1428.68016].
Reviewer: István Gaál (Debrecen)The irrationality measure of \(\pi\) is at most 7.103205334137\dots.https://www.zbmath.org/1456.111292021-04-16T16:22:00+00:00"Zeilberger, Doron"https://www.zbmath.org/authors/?q=ai:zeilberger.doron"Zudilin, Wadim"https://www.zbmath.org/authors/?q=ai:zudilin.wadimThe main result of this paper is that the irrationality measure exponent of the number \(\pi\) is less than \(7.103205334138\). The proof uses complex analysis, is based on clever calculating of special integral and is in the spirit of Salikov.
Reviewer: Jaroslav Hančl (Ostrava)Elliptic curves over finite fields with Fibonacci numbers of points.https://www.zbmath.org/1456.111162021-04-16T16:22:00+00:00"Bilu, Yuri"https://www.zbmath.org/authors/?q=ai:bilu.yuri-f"Gómez, Carlos A."https://www.zbmath.org/authors/?q=ai:gomez.carlos-alexis"Gómez, Jhonny C."https://www.zbmath.org/authors/?q=ai:gomez.jhonny-c"Luca, Florian"https://www.zbmath.org/authors/?q=ai:luca.florianThe paper studies and solves a curious problem: let \(E\)\, be an elliptic curve defined over a finite field \(\mathbb{F}_q\)\, with \(\sharp(E)=q+1-a\)\, and let us denote \(E_m(q,a);\,\, m\ge 1\)\, the number of points of \(E\)\, over \(\mathbb{F}_{q^m}\); let \(\{F_n\}_{n\ge 1}\)\, be the Fibonacci sequence. When the intersection of \(\{E_m(q,a)\}_{m\ge 1}\)\, and \(\{F_n\}_{n\ge 1}\)\, has two elements at least?, i.e. to find the solutions of \(\sharp E_{m_1} = F_{n_1}\),\, \(\sharp E_{m_2} = F_{n_2}\), etc.
Section 1 discusses the problem and formulates the obtained result (Theorem 1.1): the cardinal of the intersection is two for four couples \((q,a)\)\, and three in only a case (for \(q=a=2\)). The rest of the paper is devoted to the proof of that theorem.
Section 2 studies the equation \(E_m(q,a)=F_n\)\, in terms of linear forms in logarithms and discusses how the problem can be reduced to three cases: (i) \(q\)\, small (\(q\le 10.000\)), (ii) \(n_1\)\, small and (iii) \(m_2\)\, small. This provides a list of the possible values for \(q\).
Section 3 gathers some necessary tools regarding linear forms in logarithms and continued fractions. Assuming proved that \(n_2\le 1.000\)\, Section 4 first studies the problem for \(q\le 10.000\)\, and, using the computational package \texttt{Mathematica} finds the five solutions of Theorem 1.1. Then, for \(q> 10.000\),\, also using Mathematica, proves that there is no solution.
The rest of the paper assumes \(n_2> 1.000\)\, and Section 5 to 10 deals with the three cases (i), (ii) and (iii) and, always with the computational help of Mathematica (the paper says that ``the total calculation time for the Mathematica software for this paper was 20 days on 25 parallel desktop computers'') finishes the proof of Theorem 1.1.
Reviewer: Juan Tena Ayuso (Valladolid)A class number calculation of the \(5^{\mathrm{th}}\) layer of the cyclotomic \(\mathbb{Z}_2\)-extension of \(\mathbb{Q}(\sqrt{5})\).https://www.zbmath.org/1456.112152021-04-16T16:22:00+00:00"Aoki, Takuya"https://www.zbmath.org/authors/?q=ai:aoki.takuyaSummary: For a positive integer \(n\), let \(K_n\) be the \(n\)-th layer of the the cyclotomic \(\mathbb{Z}_2\)-extension of \(\mathbb{Q}(\sqrt{5})\), which is the real quadratic field with the minimal discriminant. We prove that the class number of \(K_5\) is 1.Corrigendum to ``On the maximum number of consecutive integers on which a character is constant''.https://www.zbmath.org/1456.111522021-04-16T16:22:00+00:00"Treviño, Enrique"https://www.zbmath.org/authors/?q=ai:trevino.enriqueCorrigendum to the author's paper [ibid. 2, No. 1, 56--72 (2012; Zbl 1280.11045)].Retraction note to: ``A determinantal expression for the Fibonacci polynomials in terms of a tridiagonal determinant''.https://www.zbmath.org/1456.110222021-04-16T16:22:00+00:00"Qi, Feng"https://www.zbmath.org/authors/?q=ai:qi.feng"Wang, Jing-Lin"https://www.zbmath.org/authors/?q=ai:wang.jing-lin"Guo, Bai-Ni"https://www.zbmath.org/authors/?q=ai:guo.bai-niThe Editor-in-Chief has retracted the original article [the authors, ibid. 45, No. 6, 1821--1829 (2019; Zbl 1423.11035)] because it significantly overlaps with a number of previously published articles [the first and third author, Matematiche 72, No. 1, 167--175 (2017; Zbl 1432.11014); the first author, \textit{V. Čerňanová} and \textit{Y. S. Semenov}, ``Some tridiagonal determinants related to central Delannoy numbers, the Chebyshev polynomials, and the Fibonacci polynomials'', Sci. Bull., Ser. A, Appl. Math. Phys., Politeh. Univ. Buchar. 81, No. 1, 123--136 (2019); the first author and \textit{A.-Q. Liu}, Acta Univ. Sapientiae, Math. 10, No. 2, 287--297 (2018; Zbl 07042987)]. This article is therefore redundant.