inria-00071634, version 1
Number of solutions to $(A^2+B^2=C^2+C)$ in a binade
N° RR-4945 (2003)
Abstract: Let us denote by Q(N,[lambda]) the number of solutions of the diophantine equation $(A^2+B^2=C^2+C)$ satisfying N<=A<=B<=C<=[lambda]N-1/2. We prove that, for [lambda] fixed and N-->infinity, there exists a constant [alpha]([lambda]) such that Q(N,[lambda])=[alpha]([lambda])N+O_[lambda](N^7/8logN). When [lambda] =2, Q(2^n-1,2) counts the number of solutions of $(A^2+B^2=C^2+C)$ with the same number, n, of binary digits; these solutions are interesting in the problem of computing the function (a,b)-->[root](a^2+b^2) in radix-2 floating-point arithmetic. By elementary arguments, Q(N,[lambda]) can be expressed in terms of four sums of the type S(u,v;f)=[SIGMA]_(u<=d<=v) ([SIGMA]_(1<=[lambda]<=f(d)) 1) where u and v are real numbers and f: [u,v] -->R is a function. These sums are estimated by a classical, but deep, method of number theory, using Fourier analysis and Kloosterman sums. This method is effective, and, in the case [lambda]=2, a precise upper bound for |Q(N,[lambda])-[alpha]([lambda])N| is given.
- 1:
- INRIA – CNRS : UMR5668 – Université Claude Bernard - Lyon I – École Normale Supérieure - Lyon
- Domain : Computer Science/Other
- Keywords : COMPUTER ARITHMETIC / CORRECT ROUNDING / DIOPHANTINE EQUATIONS
- Internal note : RR-4945
- inria-00071634, version 1
- http://hal.inria.fr/inria-00071634
- oai:hal.inria.fr:inria-00071634
- From:
- Submitted on: Tuesday, 23 May 2006 18:22:19
- Updated on: Wednesday, 31 May 2006 14:24:25




Associated documents

Export