# Computing the number of integral points in 4-dimensional ball.

[section]1. Introduction and preliminaries

A wide variety of pure and applied mathematics involve the problem of counting the number of integral points (lattice points) inside a region in space. Applications in pure mathematics are number theory, toric Hilbert functions, Kostant's partition function in representation theory and Ehrhart polynomial in combinatorics while the applied are: cryptography, integer programming, statistical contingency and mass spectroscope analysis. Perhaps the most basic case is when the region is a polytope (a convex bounded polyhedron).

[5] shows that every arrangement of spheres (and hence every central arrangemen of hyperplanes) is combinatorially equivalent to some convex polytope, [9] proved that there is a relation between the number of lattice point on a sphere and the volume of it. In [14], although a four dimensional Euclidean geometry with time as the fourth dimension was already known since Galileo Galilei's time, it was Einstein who showed that the fourth dimension, time, is essentially different from the other three dimensions. Therefore, his early creations were unrealistic. And yet, real 4D-objects have to exist, if the relativistic geometry is real. What do they look like? The difficult factorization problem for n = p.q with p and q large primes, presented as follows:

For an integer number n = p.q consider the 4-dimensional convex body B(N) = {x [member of][R.sup.4]: [x.sup.2.sub.1] + [x.sup.2.sub.2] + [x.sup.2.sub.3] + [x.sup.2.sub.4] [less than or equal to] N}, thus if we know that N = p x q, and B(N) denotes the number of lattice points in B(N).

The fast factorization of n is based on fast computing of B(N). And the application for this problem relates to RSA cryptosystems. Many optimization techniques involve a substep that counts the number of lattice points in a set S, that can be described by a set of linear constraints, i.e. S is the intersection of [z.sup.d] and a rational polyhedron [11]. The problem of counting the number of elements in S is therefore equivalent to count the number of integral points in a polytope which implies that the count is finite (since the polytope is bounded polyhedron). Different algorithms are used to find the number of lattice points since 1980 dates, all of them depend on the concept of integer programming for more see [2, 3].

Some of the basic definitions needed to consolidate results are given as follows:

Definition 1.1[10] Let Ax[less than or equal to]b where A [member of][R.sup.mxd] is a given real matrix, and b [member of][R.sup.m] is a known real vector. A set P = {x[member of][R.sup.d]: Ax[less than or equal to]b} is said to be a polyhedron. Every bounded polyhedron is said to be a polytope.

Definition 1.2[4] Let P[subset][R.sup.d] be a lattice polytope, for a positive integer t, tP = {tX: X[member of]P}.

Definition 1.3[13] Let P[subset][R.sup.d] be a lattice d-polytope. A map L:N [right arrow] N is defined by L(P, t) = card(tP[Intersection][Z.sup.d]), where card means the cardinality of (tP[Intersection][Z.sup.d]) and N is the set of natural numbers. It is seen that L(P, t) can be represented as, L(P, t) = 1 + [SIGMA][c.sub.i][t.sup.i], this polynomial is said to be the Ehrhart polynomial of a lattice d polytope P.

Theorem 1.1[13] (Pick's theorem) For d = 2, P[subset][R.sup.d] and P is an integral polyhedron. The famous formula, states that: The number of integral points in an integral polyhedron is equal to the area of the polyhedron plus half the number of integral points on the boundary of the polyhedron plus one, [absolute value of P[Intersection][Z.sup.2]] = area(P) + [absolute value of [partial derivative]P[Intersection][Z.sup.2]]/2 + 1.

This formula is useful because it is much more efficient than the direct enumeration of integral points in a polyhedron. The area of P is computed by triangulating the polyhedron. Furthermore, the boundary P is a union of finitely many straight-line intervals, and counting integral points in intervals.

Theorem 1.2[1] (Ehrhart's theorem) Let P be a convex lattice polygon and let t be a positive integer, the following equality always holds. [absolute value of P[Intersection][Z.sup.2]] = area(P)[t.sup.2] + [absolute value of [partial derivative]P[Intersection][Z.sup.2]]t/2 + 1.

Theorem 1.3[1] (Ehrhart -Macdonald reciprocity) Let P be a d polytope in [R.sup.d] with integer vertices, let L(P, t) be the number of integer points in tP, and L([P.sub.o], t) be the number of integer points in the relative interior of tP. Then let L(P, t) and L([P.sub.o], t) are polynomial functions of m of degree d satisfy L(P, 0) = 1 and L([P.sub.o], t) are polynomial functions of t of degree d that satisfy L(P, 0) = 1 and L([P.sub.o], t) = [(-1).sup.d]L(P, -t).

Theorem 1.4[8] (Jacobi 1829) The number of representations of N as a sum of four squares equates 8 times the sum of all divisors of N that are not divisible by 4.

[section]2. The proposed method

The proposed method is given in this section is to give a procedure for computing the number of integral points in 4-dimensional ball which is depending on the Ehrhart polynomials of a polytope and its properties.

Procedure 2.1. In this procedure we cover a ball in four dimension by a cube with edges a, and make use of the Ehrhart polynomial for the cube in 4-dimension. Approximately computing the number of integral points depend on the Ehrhart polynomials of the cube. First imagine a circle putting in first quadrant in a square with the same center with dimension two and get a general formula for the number of integral points include the radius of the circle and the edge of the cube which as follows:

In dimension two, let a = the edge of the square, r = radius of the circle. Ncube = number of integral points on a cube. Ncircle = number of integral points on a circle. Now if a = 2 then r = 1 and Ncube = 1. If a = 3 then r = 3/2 and Ncube = 4.

Combinatorialy the number of integral points on a circle is computed which is similar to the number of integral points on a cube. Continue in this computation until we reach to the general formula as follow:

From the general formula of the Ehrhart polynomial for a cube, which is L(P, t) = (t + 1[).sup.n] we have the number of integral points in a cube is (a-1[).sup.2], where a is the edge of the square. We didn't stop at this point but we want to of our computation and try to compute using Ehrhart polynomial for the square and then number of integral points by putting 1 in the Ehrhart polynomial as follows using theorem 2.1

[absolute value of P[Intersection][Z.sup.2]] = area(P)[t.sup.2] + [absolute value of [partial derivative]P[Intersection][Z.sup.2]] t/2 + 1,

L(P, t) = 4[t.sup.2] + 4t + 1.

The number of integral points is 9.

The number that entirely in P, can be found by using

L([P.sub.0], t) = [(-1).sup.d]L (P, -t) = [(-1).sup.2][4-[1.sup.2] + 4-1 + 1] = 1,

and so on. For dimension 3, we put a ball in a cube also we get a general formula as we are obtained it in dimension two, and the results are compared with the Ehrhart polynomial.

L(P, t) = [(t + 1).sup.d], L([P.sub.0], t) = [(t - 1).sup.d],

L([P.sub.0],2t) = [(2t - 1).sup.3], L([P.sub.0],2) = 1,

L([P.sub.0],3t) = [(3t - 1).sup.3], L([P.sub.0],3) = 8,

L([P.sub.0],4t) = [(4t - 1).sup.4], L([P.sub.0],4) = 27,

L([P.sub.0], nt) = [(nt - 1).sup.3] = number of lattice points in a sphere.

For dimension four, the general formula

L([P.sub.0], t) = (t-1[).sup.d],

L([P.sub.0], nt) = (nt-1[).sup.4]

References

[1] B. J. Braun, Ehrhart thorey for lattice polytopes, Ph.D.thesis, Washington University, 2007.

[2] J. A. De Loera, The many aspects of counting lattice points in polytopes, Mathematische Semesterberichte, 52(2005), No. 2, 175-195.

[3] J. De Loeram, R. Hemmecke, Effective lattice points counting in rational convex polytopes, Journal of symbolic computation, 53(2003), No. 8.

[4] R. Diaz, S. Robins, The Ehrhart polynomial of a lattice polytope, Annal of Math., 145(1997), 503-518.

[5] K. Fukuda, Lecture notes on oriented matroids and geometric computation, citeseerx. ist. psu. edu/viewdoc/download.

[6] Y. Kim, An algorithm for constracting magic squares, Discrete Applied Mathematics, 156 (2008).

[7] P. D. Loly, Franklin squares, a chapters in the scientific studies of magical squares, https: //www. wolframscience. com/conference/2006/presentations/materials/loly. pdf.

[8] L. Long and Y. Yang, A short proof of Milne's formulas for sums of integer squares, International journal of number theory, 1(2005), No. 4, 533-551.

[9] J. E. Mazo, A. M. odlyzko, Lattice points in high-dimensional spheres, citeseerx. ist. psu. edu/viewdoc/summary?doi = 10.1.

[10] G. L. Nemhauser and L. A. Wolsey, Integer and combinatorial optimization, John wiley and sons, Inc, 1988.

[11] A. Schrijver, Theory of linear and integer programming, John wiley and sons, 1998.

[12] A. S. Shatha, G. Adil and G. Ahlam, On the volume and integral points of a polyhedron in [R.sup.n], LAP Lambert, Academic publishing GmbH and Co. KG. Germany, 2011.

[13] R. P. Stanley, Enumerative combinatorics, wadsworth and Brooks/cole advanced Books and software, California, 1986.

[14] What does a 4-dimensional sphere look like, www.foundalis.com/phy/4dsphere.htm.

Sh. Assaad

University of Technology, Applied Mathematics, Baghdad, Iraq

E-mail: drshatha.alnajar@gmail.com

A wide variety of pure and applied mathematics involve the problem of counting the number of integral points (lattice points) inside a region in space. Applications in pure mathematics are number theory, toric Hilbert functions, Kostant's partition function in representation theory and Ehrhart polynomial in combinatorics while the applied are: cryptography, integer programming, statistical contingency and mass spectroscope analysis. Perhaps the most basic case is when the region is a polytope (a convex bounded polyhedron).

[5] shows that every arrangement of spheres (and hence every central arrangemen of hyperplanes) is combinatorially equivalent to some convex polytope, [9] proved that there is a relation between the number of lattice point on a sphere and the volume of it. In [14], although a four dimensional Euclidean geometry with time as the fourth dimension was already known since Galileo Galilei's time, it was Einstein who showed that the fourth dimension, time, is essentially different from the other three dimensions. Therefore, his early creations were unrealistic. And yet, real 4D-objects have to exist, if the relativistic geometry is real. What do they look like? The difficult factorization problem for n = p.q with p and q large primes, presented as follows:

For an integer number n = p.q consider the 4-dimensional convex body B(N) = {x [member of][R.sup.4]: [x.sup.2.sub.1] + [x.sup.2.sub.2] + [x.sup.2.sub.3] + [x.sup.2.sub.4] [less than or equal to] N}, thus if we know that N = p x q, and B(N) denotes the number of lattice points in B(N).

The fast factorization of n is based on fast computing of B(N). And the application for this problem relates to RSA cryptosystems. Many optimization techniques involve a substep that counts the number of lattice points in a set S, that can be described by a set of linear constraints, i.e. S is the intersection of [z.sup.d] and a rational polyhedron [11]. The problem of counting the number of elements in S is therefore equivalent to count the number of integral points in a polytope which implies that the count is finite (since the polytope is bounded polyhedron). Different algorithms are used to find the number of lattice points since 1980 dates, all of them depend on the concept of integer programming for more see [2, 3].

Some of the basic definitions needed to consolidate results are given as follows:

Definition 1.1[10] Let Ax[less than or equal to]b where A [member of][R.sup.mxd] is a given real matrix, and b [member of][R.sup.m] is a known real vector. A set P = {x[member of][R.sup.d]: Ax[less than or equal to]b} is said to be a polyhedron. Every bounded polyhedron is said to be a polytope.

Definition 1.2[4] Let P[subset][R.sup.d] be a lattice polytope, for a positive integer t, tP = {tX: X[member of]P}.

Definition 1.3[13] Let P[subset][R.sup.d] be a lattice d-polytope. A map L:N [right arrow] N is defined by L(P, t) = card(tP[Intersection][Z.sup.d]), where card means the cardinality of (tP[Intersection][Z.sup.d]) and N is the set of natural numbers. It is seen that L(P, t) can be represented as, L(P, t) = 1 + [SIGMA][c.sub.i][t.sup.i], this polynomial is said to be the Ehrhart polynomial of a lattice d polytope P.

Theorem 1.1[13] (Pick's theorem) For d = 2, P[subset][R.sup.d] and P is an integral polyhedron. The famous formula, states that: The number of integral points in an integral polyhedron is equal to the area of the polyhedron plus half the number of integral points on the boundary of the polyhedron plus one, [absolute value of P[Intersection][Z.sup.2]] = area(P) + [absolute value of [partial derivative]P[Intersection][Z.sup.2]]/2 + 1.

This formula is useful because it is much more efficient than the direct enumeration of integral points in a polyhedron. The area of P is computed by triangulating the polyhedron. Furthermore, the boundary P is a union of finitely many straight-line intervals, and counting integral points in intervals.

Theorem 1.2[1] (Ehrhart's theorem) Let P be a convex lattice polygon and let t be a positive integer, the following equality always holds. [absolute value of P[Intersection][Z.sup.2]] = area(P)[t.sup.2] + [absolute value of [partial derivative]P[Intersection][Z.sup.2]]t/2 + 1.

Theorem 1.3[1] (Ehrhart -Macdonald reciprocity) Let P be a d polytope in [R.sup.d] with integer vertices, let L(P, t) be the number of integer points in tP, and L([P.sub.o], t) be the number of integer points in the relative interior of tP. Then let L(P, t) and L([P.sub.o], t) are polynomial functions of m of degree d satisfy L(P, 0) = 1 and L([P.sub.o], t) are polynomial functions of t of degree d that satisfy L(P, 0) = 1 and L([P.sub.o], t) = [(-1).sup.d]L(P, -t).

Theorem 1.4[8] (Jacobi 1829) The number of representations of N as a sum of four squares equates 8 times the sum of all divisors of N that are not divisible by 4.

[section]2. The proposed method

The proposed method is given in this section is to give a procedure for computing the number of integral points in 4-dimensional ball which is depending on the Ehrhart polynomials of a polytope and its properties.

Procedure 2.1. In this procedure we cover a ball in four dimension by a cube with edges a, and make use of the Ehrhart polynomial for the cube in 4-dimension. Approximately computing the number of integral points depend on the Ehrhart polynomials of the cube. First imagine a circle putting in first quadrant in a square with the same center with dimension two and get a general formula for the number of integral points include the radius of the circle and the edge of the cube which as follows:

In dimension two, let a = the edge of the square, r = radius of the circle. Ncube = number of integral points on a cube. Ncircle = number of integral points on a circle. Now if a = 2 then r = 1 and Ncube = 1. If a = 3 then r = 3/2 and Ncube = 4.

Combinatorialy the number of integral points on a circle is computed which is similar to the number of integral points on a cube. Continue in this computation until we reach to the general formula as follow:

From the general formula of the Ehrhart polynomial for a cube, which is L(P, t) = (t + 1[).sup.n] we have the number of integral points in a cube is (a-1[).sup.2], where a is the edge of the square. We didn't stop at this point but we want to of our computation and try to compute using Ehrhart polynomial for the square and then number of integral points by putting 1 in the Ehrhart polynomial as follows using theorem 2.1

[absolute value of P[Intersection][Z.sup.2]] = area(P)[t.sup.2] + [absolute value of [partial derivative]P[Intersection][Z.sup.2]] t/2 + 1,

L(P, t) = 4[t.sup.2] + 4t + 1.

The number of integral points is 9.

The number that entirely in P, can be found by using

L([P.sub.0], t) = [(-1).sup.d]L (P, -t) = [(-1).sup.2][4-[1.sup.2] + 4-1 + 1] = 1,

and so on. For dimension 3, we put a ball in a cube also we get a general formula as we are obtained it in dimension two, and the results are compared with the Ehrhart polynomial.

L(P, t) = [(t + 1).sup.d], L([P.sub.0], t) = [(t - 1).sup.d],

L([P.sub.0],2t) = [(2t - 1).sup.3], L([P.sub.0],2) = 1,

L([P.sub.0],3t) = [(3t - 1).sup.3], L([P.sub.0],3) = 8,

L([P.sub.0],4t) = [(4t - 1).sup.4], L([P.sub.0],4) = 27,

L([P.sub.0], nt) = [(nt - 1).sup.3] = number of lattice points in a sphere.

For dimension four, the general formula

L([P.sub.0], t) = (t-1[).sup.d],

L([P.sub.0], nt) = (nt-1[).sup.4]

References

[1] B. J. Braun, Ehrhart thorey for lattice polytopes, Ph.D.thesis, Washington University, 2007.

[2] J. A. De Loera, The many aspects of counting lattice points in polytopes, Mathematische Semesterberichte, 52(2005), No. 2, 175-195.

[3] J. De Loeram, R. Hemmecke, Effective lattice points counting in rational convex polytopes, Journal of symbolic computation, 53(2003), No. 8.

[4] R. Diaz, S. Robins, The Ehrhart polynomial of a lattice polytope, Annal of Math., 145(1997), 503-518.

[5] K. Fukuda, Lecture notes on oriented matroids and geometric computation, citeseerx. ist. psu. edu/viewdoc/download.

[6] Y. Kim, An algorithm for constracting magic squares, Discrete Applied Mathematics, 156 (2008).

[7] P. D. Loly, Franklin squares, a chapters in the scientific studies of magical squares, https: //www. wolframscience. com/conference/2006/presentations/materials/loly. pdf.

[8] L. Long and Y. Yang, A short proof of Milne's formulas for sums of integer squares, International journal of number theory, 1(2005), No. 4, 533-551.

[9] J. E. Mazo, A. M. odlyzko, Lattice points in high-dimensional spheres, citeseerx. ist. psu. edu/viewdoc/summary?doi = 10.1.

[10] G. L. Nemhauser and L. A. Wolsey, Integer and combinatorial optimization, John wiley and sons, Inc, 1988.

[11] A. Schrijver, Theory of linear and integer programming, John wiley and sons, 1998.

[12] A. S. Shatha, G. Adil and G. Ahlam, On the volume and integral points of a polyhedron in [R.sup.n], LAP Lambert, Academic publishing GmbH and Co. KG. Germany, 2011.

[13] R. P. Stanley, Enumerative combinatorics, wadsworth and Brooks/cole advanced Books and software, California, 1986.

[14] What does a 4-dimensional sphere look like, www.foundalis.com/phy/4dsphere.htm.

Sh. Assaad

University of Technology, Applied Mathematics, Baghdad, Iraq

E-mail: drshatha.alnajar@gmail.com

Table 1. Number of lattice points in dimension 2 n a r Ncube Ncircle 1 2 1 1 1 3 3/2 4 4 4 2 9 9 5 5/2 16 16 6 3 25 25 7 7/2 36 36 8 4 49 49 9 9/2 64 64 Table 2. Number of lattice points in dimension 3 n a r Ncube Ncircle 1 2 1 1 1 3 3/2 8 8 4 2 27 27 5 5/2 64 64 6 3 [5.sup.3] [5.sup.3] 7 7/2 [6.sup.3] [6.sup.3] 8 4 [7.sup.3] [7.sup.3] 9 9/2 [8.sup.3] [8.sup.3] Table 3. Number of lattice points in dimension 4 n a r Ncube Ncircle 1 2 1 1 1 3 3/2 [2.sup.4] [2.sup.4] 4 2 [3.sup.4] [3.sup.4] 5 5/2 [4.sup.4] [4.sup.4] 6 3 [5.sup.4] [5.sup.4] 7 7/2 [6.sup.4] [6.sup.4] 8 4 [7.sup.4] [7.sup.4] 9 9/2 [8.sup.4] [8.sup.4]

Printer friendly Cite/link Email Feedback | |

Author: | Assaad, Sh. |
---|---|

Publication: | Scientia Magna |

Article Type: | Report |

Geographic Code: | 4EUGE |

Date: | Mar 1, 2013 |

Words: | 1908 |

Previous Article: | A view on ordered intuitionistic Fuzzy smooth quasi uniform basically disconnected spaces. |

Next Article: | Turan Type inequalities for (p, q)-Gamma function. |

Topics: |