Finite Euclidean graphs and Ramanujan graphs

We consider finite analogues of Euclidean graphs in a more general setting than that considered in [A. Medrano, P. Myers, H.M. Stark, A. Terras, Finite analogues of Euclidean space, J. Comput. Appl. Math. 68 (1996) 221–238] and we obtain many new examples of Ramanujan graphs. In order to prove these results, we use the previous work of [W.M. Kwok, Character tables of association schemes of affine type, European J. Combin. 13 (1992) 167–185] calculating the character tables of certain association schemes of affine type. A key observation is that we can obtain better estimates for the ordinary Kloosterman sum K(a,b;q)K(a,b;q). In particular, we always achieve |K(a,b;q)|<2q, and |K(a,b;q)|≤2q−2 in many (but not all) of the cases, instead of the well known |K(a,b;q)|≤2q. Also, we use the ideas of controlling association schemes, and the Ennola type dualities, in our previous work on the character tables of commutative association schemes. The method in this paper will be used to construct many more new examples of families of Ramanujan graphs in the subsequent paper.