Given a linear discrete time system, necessary and sufficient conditions for the existence of a linear or nonlinear controller, which satisfies a specified closed-loop H-infinity norm bound, are stated in terms of the solutions to two uncoupled algebraic discrete Riccati equations of the order of the system. State-space formulae for all the stabilizing controllers, some of the order of the system, which satisfy an achievable bound are also given. In this first part of the paper, new growth and convergence properties of the solution to a time-varying discrete Riccati equation are used to derive the necessary and sufficient conditions for the existence of a solution in the full information case. These properties generalize those of the corresponding discrete Riccati equation related to the LQR problem. In the second part of the paper, a non-standard estimation problem is posed and salved. This problem arises as a novel reinterpretation of the H-infinity norm objective. Its solution can be used to reduce a partial information to a full information control problem. Our approach to solving the H-infinity output feedback control problem is based on this result. This approach, the dual of that typically used in H-infinity control theory, yields significant new insights into the H-infinity regulation problem. Minimax difference game theory is central to the developments of this paper and it is shown that minimax, not saddle point game theory, provides the proper framework to solve the H-infinity regulation problem.