Mathematica Asked by Stanley Rabinowitz on July 22, 2020

Most of the time when I use FindIntegerNullVector with inexact numbers, I get useful results.

But occasionally, it seems to miss finding a simple null vector.

Example:

```
a = 13.4414592345679;
b = 3.402468500410153;
c = 3.7037718641975403;
d = 12.34799099999999;
Quiet[FindIntegerNullVector[{a b, c d}, 10]]
```

finds no integer relationship even though a b-c d < 3 * 10^(-14).

I was expecting a result of {1, -1}.

What am I doing wrong and/or how can I fix this line so that it will recognize that the two arguments are approximately equal?

I have tried varying WorkingPrecision and ZeroTest.

This seems to work on the case at hand:

```
FindIntegerNullVector[SetPrecision[{a b, c d}, 15] 10]
```

`(* {1, -1} *)`

But why the precision `15`

? The problem is to find, for real numbers $A$ and $B$, integers $x$ and $y$ such that
$$Ax+By=0 ,.tag{1}$$
Suppose $A^*,,B^*$ are floating-point approximations of $A,B$ resp. Then the problem is to find an integer point $(x^*,y^*)$ such that the line in the real $xy$-plane given by equation (1) passes "close enough" to $(x^*,y^*)$, where close enough depends on the error of the approximations $A^*,,B^*$. `FindIntegerNullVector`

does this with some notion of "close enough" depending on the precision of the input.

Below is an adaptation `fINS`

of an example in the documentation for `LatticeReduce`

to solve the `FindIntegerNullVector`

problem that diminishes the precision until we get a solution with a relatively small error (rough 1 ulp at the current precision). In the couple of tests in which there is an integer null relation, it tends to overestimate the reduction in precision needed (pick a precision that is lower than necessary). In the one totally random example, it did the reverse. Consequently, `fINS`

only approximates the precision needed for `FindIntegerNullVector`

to reproduce the result of `LatticeReduce`

/`fINS`

.

```
fINS[z_?VectorQ] := Module[{a, b, err},
a = IdentityMatrix[Length[z]];
b = {{2, 2, 2}}; (* dummy values: fails While test *)
err = 1;
While[Abs[b[[1, -1]]] > 1,
b = PadRight[a, {Automatic, Length@z + 1},
List /@ Round[-10^Precision[z]/err*z]]; (* scale the FP vec z and round *)
(* which simulates FP round-off *)
(* in integers *)
b = LatticeReduce[b];
If[b[[1, -1]] != 0, err *= b[[1, -1]]];
];
{b[[1, ;; -2]], 10.^-Precision[z] * err}
];
```

Note `fINS`

returns the null sequence and the estimate of the error tolerance needed.

```
{sol, tol} = fINS[{a b, c d}]
```

`(* {{-1, 1}, 2.84217*10^-14} *)`

Map the tolerance to `Precision`

:

```
reltol = Abs@tol/Max@Abs@{a b, c d};
prec = -Log10[reltol]
```

`(* 15.2066 *)`

```
FindIntegerNullVector[SetPrecision[{a b, c d}, prec], 10]
```

`(* {1, -1} *)`

We can increase the precision a little; too much, and `FindIntegerNullVector`

fails:

```
prec = -Log10[reltol/2];
FindIntegerNullVector[SetPrecision[{a b, c d}, prec], 10]
prec = -Log10[reltol/5];
FindIntegerNullVector[SetPrecision[{a b, c d}, prec], 10]
```

`(* {1, -1} *)`

FindIntegerNullVector::norel: There is no integer null vector for {45.73414164516444,45.73414164516441} with norm less than or equal to 10.

`(* FindIntegerNullVector[{45.73414164516444, 45.73414164516441}, 10] *)`

`LatticeReduce`

example perturbed by noise.First, the exact problem:

```
FindIntegerNullVector[{Cos[4], Cos[1]^4, Cos[1]^2, 1}]
```

`(* {1, -8, 8, -1} *)`

The perturbed problem: a tolerance of around `10^-14`

or precision of around `14`

should be needed.

```
SeedRandom[1];
coeffs = N@{Cos[4], Cos[1]^4, Cos[1]^2, 1} + RandomReal[10^-14, 4];
{sol, tol} = fINS[coeffs]
reltol = Abs@tol/Max@Abs@coeffs;
prec = -Log10[reltol];
```

`(* {{-1, 8, -8, 1}, 6.15064*10^-13} *)`

```
FindIntegerNullVector[SetPrecision[coeffs, prec]]
FindIntegerNullVector[coeffs]
```

`(* {1, -8, 8, -1} {78257927, -626063069, 626063140, -78257876} *)`

In this case the precision can be raised more:

```
prec = -Log10[reltol/10];
FindIntegerNullVector[SetPrecision[coeffs, prec]]
prec = -Log10[reltol/50];
FindIntegerNullVector[SetPrecision[coeffs, prec]]
```

`(* {1, -8, 8, -1} {-36655, -42915, 67969, -40144} *)`

No relationship is expected but `FindIntegerNullVector`

finds one with large norm. The precision in this particular case needs to be lowered to get `FindIntegerNullVector`

to return the same result as `fINS`

```
SeedRandom[0];
coeffs = RandomReal[1, 4];
{sol, tol} = fINS[coeffs]
reltol = Abs@tol/Max@Abs@coeffs;
prec = -Log10[reltol ];
FindIntegerNullVector[SetPrecision[coeffs, prec]]
FindIntegerNullVector[coeffs]
```

`(* {{6, -6, -1, 1}, 0.0000326167} <-- prec ~ 4.3 {-12, 7, 0, 6} {-18811, -20158, 21650, 18102} *)`

To get the smaller norm solution, we need to lower the precision:

```
Norm /@ N@{{-6, 6, 1, -1}, {-12, 7, 0, 6}}
```

`(* {8.60233, 15.1327} *)`

```
FindIntegerNullVector[SetPrecision[coeffs, prec], 12]
FindIntegerNullVector[SetPrecision[coeffs, prec - 0.3], 12]
```

FindIntegerNullVector::rnf: FindIntegerNullVector has not found an integer null vector for {0.6525,0.6331,0.6828,0.5664} with norm less than or equal to 12.

`(* FindIntegerNullVector[{0.6525, 0.6331, 0.6828, 0.5664}, 12] *)`

`(* {-6, 6, 1, -1} *)`

Correct answer by Michael E2 on July 22, 2020

A solution is give the built-in the right amout of toleranz with a constant in another dimension:

```
FindIntegerNullVector[{a b, c d, 10^-14}, 10]
{1, -1, -3}
```

Answered by Steffen Jaeschke on July 22, 2020

Get help from others!

Recent Questions

- How can I transform graph image into a tikzpicture LaTeX code?
- How Do I Get The Ifruit App Off Of Gta 5 / Grand Theft Auto 5
- Iv’e designed a space elevator using a series of lasers. do you know anybody i could submit the designs too that could manufacture the concept and put it to use
- Need help finding a book. Female OP protagonist, magic
- Why is the WWF pending games (“Your turn”) area replaced w/ a column of “Bonus & Reward”gift boxes?

Recent Answers

- Joshua Engel on Why fry rice before boiling?
- Peter Machado on Why fry rice before boiling?
- Jon Church on Why fry rice before boiling?
- Lex on Does Google Analytics track 404 page responses as valid page views?
- haakon.io on Why fry rice before boiling?

© 2024 TransWikia.com. All rights reserved. Sites we Love: PCI Database, UKBizDB, Menu Kuliner, Sharing RPP