This paper presents Lyapunov characterizations of uniform output-to-state stability and uniform input-output-to-state stability (IOSS) (with respect to disturbances) for discrete-time (DT) nonlinear systems. We show the equivalence of the following three properties for DT systems: uniform IOSS, existence of a smooth Lyapunov function for uniform IOSS, and existence of a (state-)norm estimator. This equivalence result is a DT counterpart of Krichman et al. [2001. Input-output-to-state stability. SIAM Journal on Control and Optimization 39, 1874-1928. Theorem 2.41 and a generalization of Jiang and Wang [2002. A converse Lyapunov theorem for discrete-time systems with disturbances. Systems and Control Letters 45, 49-58. Theorem 1.1] and Jiand and Wang [2001. Input-to-state stability for discrete-time nonlinear systems. Automatica 37, 857-869. Theorem I, I double left right arrow 4]. (C) 2007 Elsevier Ltd. All rights reserved.