:

## Integer points in curved regions

Maple 2015

IntegerPoints2  procedure generalizes  IntegerPoints1  procedure and finds all the integer points inside a bounded curved region of arbitrary dimension.  We also use a brute force method, but to find the ranges for each variable  Optimization[Minimize]  and   Optimization[Maximize]  is used instead of  simplex[minimize]  or  simplex[minimize] .

Required parameters of the procedure: SN is a set or a list of  inequalities and/or equations with any number of variables, the Var is the list of variables. Bound   is an optional parameter - list of ranges for each variable in the event, if  Optimization[Minimize/Maximize]  fails. By default  Bound  is NULL.

If all constraints are linear, then in this case it is recommended to use  IntegerPoints1  procedure, as it is better to monitor specific cases (no solutions or an infinite number of solutions for an unbounded region).

Code of the procedure:

IntegerPoints2 := proc (SN::{list, set}, Var::(list(symbol)), Bound::(list(range)) := NULL)

local SN1, sn, n, i, p, q, xl, xr, Xl, Xr, X, T, k, t, S;

uses Optimization, combinat;

n := nops(Var);

if Bound = NULL then

SN1 := SN;

for sn in SN1 do

if type(sn, `<`) then

SN1 := subs(sn = (`<=`(op(sn))), SN1) fi od;

for i to n do

p := Minimize(Var[i], SN1); q := Maximize(Var[i], SN1);

xl[i] := eval(Var[i], p[2]); xr[i] := eval(Var[i], q[2]) od else

assign(seq(xl[i] = lhs(Bound[i]), i = 1 .. n));

assign(seq(xr[i] = rhs(Bound[i]), i = 1 .. n)) fi;

Xl := map(floor, convert(xl, list)); Xr := map(ceil, convert(xr, list));

X := [seq([\$ Xl[i] .. Xr[i]], i = 1 .. n)];

T := cartprod(X); S := table();

for k while not T[finished] do

t := T[nextvalue]();

if convert(eval(SN, zip(`=`, Var, t)), `and`) then

S[k] := t fi od;

convert(S, set);

end proc:

In the first example, we find all the integer points in the four-dimensional ball of radius 10:

Ball := IntegerPoints2({x1^2+x2^2+x3^2+x4^2 < 10^2}, [x1, x2, x3, x4]):  # All the integer points

nops(Ball);  # The total number of the integer points

seq(Ball[1000*n], n = 1 .. 10);  # Some points

48945

[-8, 2, 0, -1], [-7, 0, 1, -3], [-6, -4, -6, 2], [-6, 1, 1, 1], [-5, -6, -2, 4], [-5, -1, 2, 0],

[-5, 4, -6, -2], [-4, -5, 1, 5], [-4, -1, 6, 1], [-4, 3, 5, 6]

In the second example, with the visualization we find all the integer points in the inside intersection of  a cone and a cylinder:

A := <1, 0, 0; 0, (1/2)*sqrt(3), -1/2; 0, 1/2, (1/2)*sqrt(3)>:  # Matrix of rotation around x-axis at Pi/6 radians

f := unapply(A^(-1) . <x, y, z-4>, x, y, z):

S0 := {4*x^2+4*y^2 < z^2}:  # The inner of the cone

S1 := {x^2+z^2 < 4}:  # The inner of the cylinder

S2 := evalf(eval(S1, {x = f(x, y, z)[1], y = f(x, y, z)[2], z = f(x, y, z)[3]})):

S := IntegerPoints2(`union`(S0, S2), [x, y, z]);  # The integer points inside of the intersection of the cone and the rotated cylinder

Points := plots[pointplot3d](S, color = red, symbol = solidsphere, symbolsize = 8):

Sp := plot3d([r*cos(phi), r*sin(phi), 2*r], phi = 0 .. 2*Pi, r = 0 .. 5, style = surface, color = "LightBlue", transparency = 0.7):

F := plottools[transform]((x, y, z)->convert(A . <x, y, z>+<0, 0, 4>, list)):

S11 := plot3d([2*cos(t), y, 2*sin(t)], t = 0 .. 2*Pi, y = -4 .. 7, style = surface, color = "LightBlue", transparency = 0.7):

plots[display]([F(S11), Sp, Points], scaling = constrained, orientation = [25, 75], axes = normal);

In the third example, we are looking for the integer points in a non-convex area between two parabolas. Here we have to specify ourselves the ranges to enumeration (Optimization[Minimize] command fails for this example):

P := IntegerPoints2([y > (-x^2)*(1/2)+2, y < -x^2+8], [x, y], [-4 .. 4, -4 .. 8]);

A := plots[pointplot](P, color = red, symbol = solidcircle, symbolsize = 10):

B := plot([(-x^2)*(1/2)+2, -x^2+8], x = -4 .. 4, -5 .. 9, color = blue):

plots[display](A, B, scaling = constrained);

﻿