An improved lower bound for approximating Shortest Integer Relation in ℓ∞ norm (SIR∞)

In this paper, we show that assuming P ≠ NP, it is hard to approximate the Shortest Integer Relation in ℓ∞ norm (SIR∞) within a factor nc/loglogn for some constant c>0 where n is the dimension of the given vector. This improves on the best previous result. The best result so far gave (logn)1/2−ε2 factor hardness by Rössner and Seifert [C. Rössner, J.P. Seifert, On the hardness of approximating shortest integer relations among rational numbers, Theoret. Comput. Sci. 209 (1–2) (1998) 287–297], where ε>0 is an arbitrarily small constant. By the improved result of SIR∞, we also improve on the inapproximability factor of Good Diophantine Approximations in ℓ∞ norm (GDA∞) to nc/loglogn.